Problemas algorítmicos de aparência simplificada facilitados por teoremas

28

Estou procurando bons exemplos, nos quais ocorre o seguinte fenômeno: (1) Um problema algorítmico parece difícil, se você quiser resolvê-lo trabalhando com as definições e usando apenas resultados padrão. (2) Por outro lado, fica fácil se você conhece alguns teoremas (não tão padrão).

O objetivo disso é ilustrar para os alunos que aprender mais teoremas pode ser útil, mesmo para aqueles que estão fora do campo da teoria (como engenheiros de software, engenheiros de computação etc.). Aqui está um exemplo:

Pergunta: Dados os números inteiros , existe um gráfico vertex (e, nesse caso, encontre um), de modo que sua conectividade de vértice seja , sua conectividade de borda seja e seu grau mínimo seja ?n k l dn,k,l,dnkld

Observe que exigimos que os parâmetros sejam exatamente iguais aos números fornecidos, eles não são apenas limites. Se você quiser resolver isso do zero, pode parecer um pouco difícil. Por outro lado, se você está familiarizado com o seguinte teorema (consulte Teoria dos grafos extremos por B. Bollobas), a situação se torna bem diferente.

Teorema: Seja inteiros. Existe um gráfico -vertex com conectividade de vértices , conectividade de borda e grau mínimo , se e somente se uma das seguintes condições for atendida:n k l dn,k,l,dnkld

  • 0kld<n/2 ,
  • 12d+2nkl=d<n1
  • k=l=d=n1.

Essas condições são muito fáceis de verificar, sendo simples desigualdades entre os parâmetros de entrada, para que a questão da existência possa ser respondida sem esforço. Além disso, a prova do teorema é construtiva, resolvendo também a questão da construção. Por outro lado, esse resultado não parece padrão o suficiente, para que você possa esperar que todos saibam disso.

Você pode fornecer mais exemplos nesse espírito, onde conhecer um teorema (não tão padrão) simplifica muito uma tarefa?

Andras Farago
fonte
1
Não sei se entendi completamente suas perguntas. O exemplo que você dá é um problema não trivial para o qual Bollobas forneceu um algoritmo (o que implica uma caracterização). Assim, a minha impressão com o seu exemplo é que qualquer não-trivial algoritmo será uma resposta ...
de Bruno
3
Primalidade e o teorema de AKS.
Lamine
@Bruno: O que eu quero dizer é que a tarefa algorítmica se torna muito mais fácil se você conhece um teorema, que não é bem conhecido, então talvez nunca tenha ouvido falar dele. O exemplo apresentado não é perfeito no sentido em que aqui o teorema não apenas ajuda, mas realmente resolve o problema. O que realmente estou procurando é quando um teorema ajuda, fornece algum atalho útil, mas não resolve completamente o problema.
Andras Farago
3
Wiki da comunidade?
13134 Joshua Grochow
1
Teorema de Robertson-Seymour, também conjecturas que facilitam encontrar deterministicamente números primos.
22414 Kaveh

Respostas:

31

Decidir isomorfismo de grupos simples , dado por suas tabuadas de multiplicação. O fato de que isso pode ser feito em tempo polinomial decorre diretamente do fato de que todos os grupos simples finitos podem ser gerados por no máximo 2 elementos, e atualmente a única prova conhecida desse fato usa a Classificação de Grupos Simples Finitos (talvez o maior teorema - em termos de autores, trabalhos e páginas - já comprovados).

Joshua Grochow
fonte
3
Este é um excelente exemplo! BTW os comentários a esta reivindicação resposta que, em certo sentido este teorema é quase tão duro como a classificação: mathoverflow.net/a/59216/35733
Sasho Nikolov
32

Se eu entendi sua pergunta corretamente, um exemplo canônico seria decidir se um gráfico tem um circuito euleriano: equivalente a verificar se está conectado e todos os vértices têm grau uniforme.GGG

Sasho Nikolov
fonte
20

Esta tarde, eu estava lendo Stringologia - a teoria das cordas "Real" .

Problema: Se e são duas cadeias de mais de algum alfabeto quando existem alguns inteiros positivos , tais que .xym,nxm=yn

Teorema: Existem inteiros positivos tais que se e somente se .m,nxm=ynxy=yx

Pratik Deoghare
fonte
9

Encontrar o número de raízes reais (distintas) de um polinômio real, em todo of ou em um determinado intervalo. O teorema de Sturm diz que uma sequência de polinômios que atende a um pequeno número de requisitos pode ser usada para contar o número de raízes reais de um polinômio com coeficientes reais.

Então, tudo o que você precisa fazer é construir essa sequência (o que não é muito difícil, mas requer alguns casos extremos e manipulação do caso de polinômios não separáveis), e Bob é seu tio.

Surpreendentemente, poucas pessoas sabem sobre esse resultado, apesar de ser bastante antigo (1829). É usado em muitos sistemas de álgebra computacional, mas todos os professores de matemática da minha universidade a quem perguntei não conheciam o Teorema de Sturm ou apenas o conheciam pelo nome e que têm algo a ver com as raízes dos polinômios.

A maioria das pessoas fica bastante surpresa quando você lhes diz que algo como contar exatamente as raízes reais é fácil e não exige nenhuma aproximação, considerando que encontrar raízes é muito mais difícil. (Lembre-se de que para polinômios de grau ≥ 5, não existe sequer uma fórmula "adequada" para as raízes)

Manuel Eberl
fonte
9

Teorema: Todo grafo planar possui um vértice com grau no máximo 5.

Problema: projete uma representação de gráficos planares onde podemos verificar se é uma aresta no tempo .O(n)(u,v)O(1)

Podemos remover o vértice com grau no máximo 5 e adicioná-lo a uma lista como chave e seus vizinhos como valores. O gráfico restante também é plano e possui um vértice com grau no máximo 5. Portanto, o espaço consumido é no máximo . Podemos verificar se está na lista de adjacências de ; caso contrário, podemos verificar se está na lista de adjacências de . Isso leva no máximo etapas.5nuvvu10

Pratik Deoghare
fonte
5
Com um pouco mais de cuidado, você pode reduzir o tamanho da lista armazenada em cada vértice para 3 e o número de etapas para verificar a adjacência em 6. Consulte: Orientações planares com baixo grau de compactação e compactação de matrizes de adjacência. M. Chrobak e D. Eppstein. Theor. Comp. Sci. 86 (2): 243–266, 1991. ics.uci.edu/~eppstein/pubs/ChrEpp-TCS-91.pdf
David Eppstein
7

Penso que o póster desta categoria, pelo menos no que diz respeito à assimetria de dificuldade, é o seguinte problema:

Dado um gráfico planar , é 4 colorido?GG

O teorema das quatro cores simplifica o algoritmo para return true.

Jonas Kölker
fonte
6

Se um polinômio real (multivariado) pode ser expresso como uma soma de quadrados de polinômios reais pode ser resolvido por redução à programação semi-definida. Precisa conhecer o SDP e esse SDP pode ser resolvido com eficiência.p

Chandra Chekuri
fonte
5

Outro exemplo: dado um gráfico não direcionado, ele tem um corte mínimo no qual todas as arestas são separadas? Se sim, encontre um.

À primeira vista, isso pode parecer difícil. Torna-se fácil, no entanto, se você souber o resultado que um gráfico vértice não direcionado pode ter no máximo cortes mínimos e todos eles podem ser listados em tempo polinomial.nn(n1)/2

Pode ser estendido para cortes quase mínimos, que são maiores que o corte mínimo, mas no máximo por um fator constante. Seu número ainda é limitado por um polinômio.

(Não procurei uma referência, lembro-me de que esses resultados se devem a D. Karger.)

Andras Farago
fonte
4

Problema: Satifsiabilidade de uma fórmula MSO (lógica monádica de segunda ordem) sobre palavras finitas.

Teorema: MSO é equivalente a autômatos finitos sobre palavras finitas.

O acima pode ser elevado a palavras infinitas, árvores finitas, árvores infinitas.

Denis
fonte
4

Um exemplo um pouco mais complicado: fatoração de matriz não negativa , quando a classificação não negativa é constante.

Digamos que eu lhe forneça uma matriz juntamente com a promessa de que existem não negativos , modo que . O problema é encontrar tais fatoração de um para . U M m × k V M k × n A = U V AAMm×nUMm×kVMk×nA=UVA

Com algumas linhas de álgebra linear elementar, você pode reduzir o problema para resolver um sistema de desigualdades polinomiais em variáveis , em que é a classificação não negativa da matriz que você deseja fatorar.rO(r2)r

(mn)O(r2)UV(mn)o(r)

zotachidil
fonte
4

Decisional Diffie Hellman

(g,ga,gb,gc)gGgc=gab

Sob as premissas padrão de dureza do problema de log discreto, esse problema também pode parecer difícil.

e(g,gc)=?e(ga,gb)

e:G×GGT

Mais sobre isso pode ser lido em O problema decisivo do homem das trevas, Boneh'98 ou uma pesquisa no Google em Pairings

Subhayan
fonte
3

(Trivialmente) a existência de um Equilíbrio de Nash em um jogo finito, um número par de Caminhos Hamiltonianos em um gráfico cúbico, vários tipos de pontos fixos, comparações decentemente equilibradas em ordens parciais e muitos outros problemas de PPAD.

Yonatan N
fonte
A existência de Equilíbrio de Nash - e muitas das outras provas da existência que caracterizaram PPAD - não parecem fazer qualquer um desses problemas mais fáceis de resolver através de algoritmos ...
Joshua Grochow
1
Eu estava me referindo à versão de decisão desses problemas.
precisa
2

((V,E),s,t)EEst(V,E)E

st(V,E)st

Máx.
fonte
1
Pode-se dizer que o fluxo é fácil se você souber que o LP é fácil. Assim, dois grandes teoremas (LP no tempo de polietileno e maxflow-mincut) nos permitem calcular min-recortes.
Chandra Chekuri
@ChandraChekuri, meu sentimento pessoal é que isso não se encaixa bem na questão: o teorema de que o LP é solucionável no polytime não nos ajuda a realmente construir um algoritmo para min-cuts. Precisamos do algoritmo LP real.
Max
Na verdade não. Se você conseguir encontrar o valor de min-cut em um determinado gráfico com eficiência, poderá usar esse algoritmo para encontrar o próprio corte real.
Chandra Chekuri
2

Aqui está outro exemplo: dado um gráfico simples não direcionado, decida se ele possui dois circuitos separados por vértices.

23

3K5K3,n3

Como é fácil verificar se um gráfico é um dos gráficos permitidos pelo Teorema, isso nos fornece um algoritmo de tempo polinomial para o problema de decisão.

Notas: (1) A prova do teorema não é nada fácil. (2) Depois que decidimos que existem dois circuitos disjuntos, parece menos claro como resolver o problema de pesquisa associado , ou seja, como realmente encontrar esses circuitos. O teorema não aconselha diretamente isso.

Andras Farago
fonte
1

exemplos menos complexos: existem algumas propriedades semelhantes a teoremas que mostram que algoritmos gananciosos para alguns problemas são ótimos. não é tão óbvio para os não iniciados que uma árvore de abrangência mínima possa ser encontrada por um algoritmo ganancioso. um pouco semelhante conceitualmente é o algoritmo de Dijkstra para encontrar o caminho mais curto em um gráfico. na verdade, em ambos os casos, os "teoremas" associados são quase os mesmos que os algoritmos.

vzn
fonte
Acho que essa será uma resposta melhor se, por exemplo, você incluir uma declaração da propriedade cut do MST e mencionar como isso implica a correção de toda uma classe de algoritmos gananciosos do MST.
Sasho Nikolov
Propriedade de corte MST listada na wikipedia, na pág. talvez você possa refutar outras generalizações não abordadas aqui. btw lembro a pergunta pediu exemplos que servem "aqueles que estão fora do campo teoria" (outros exemplos agradáveis dadas podem ser muito avançado para pessoas de fora)
vzn
TeTeABeE(A,B)
1

Encontre a sequência dos números de Fibonacci que são o produto de outros números de Fibonacci. Por exemplo, o número de Fibonacci 8 está na sequência porque 8 = 2 * 2 * 2 e 2 é um número de Fibonacci que não é igual a 8. O número de Fibonacci 144 está na sequência porque 144 = 3 * 3 * 2 * 2 * 2 * 2 e 2 e 3 são números de Fibonacci que não são iguais a 144.

O teorema de Carmichael implica que 8 e 144 são os únicos termos dessa sequência.

Bob Lyons
fonte