Problemas que parecem exponenciais, mas são P

12

Estou tentando criar uma lista de algoritmos / problemas que são "excepcionalmente úteis", como resolver problemas que 'parecem' muito exponenciais por natureza, mas que têm algum algoritmo particularmente inteligente que finalmente os resolve. Exemplos do que quero dizer:

  • Programação Linear (O algoritmo simplex é tempo exponencial; demorou muito tempo para encontrar uma solução de tempo polinomial!)
  • De maneira mais geral, Programação Semidefinida
  • Teste de primazia
  • 2-SAT e HORNSAT
  • Determinantes da computação (se isso não parecer difícil, considere o permanente)
  • Encontrar combinações perfeitas
  • Uma variedade de problemas teóricos de grupos difíceis que podem ser realizados usando a Classificação de grupos simples finitos
  • Uma variedade de problemas gráficos difíceis que podem ser resolvidos usando caracterizações Menores Proibidas Menores (incorporação em uma superfície arbitrária; delimitação de largura de árvore e largura de filial; gráficos redutíveis Delta-Wye)
  • Computando exponenciais em um grupo delimitado (isto é, computando em \ log b etapas, como realizado por quadrados repetidos)umabmodkregistrob
  • Cálculos baseados no algoritmo LLL. (Como um caso especial: algoritmo euclidiano. Como um caso mais geral: algoritmos PSLQ ou HJLS.)
  • Problemas de restrição sem termos de Taylor (?). Admito que não entendo completamente isso, mas parece que provavelmente inclui os casos 2-SAT / HORNSAT acima e qualquer álgebra linear sobre campos finitos. Veja aqui para uma postagem mais longa
  • Problemas computáveis ​​através de reduções holográficas .

Como menção honrosa, eu também mencionaria o isomorfismo do gráfico, porque ainda é muito fácil ( ), e equivalente a muitos outros problemas de isomorfismo:nregistro2n

  • Dígrafos / multigráficos / hipergráficos (uma espécie de problema "mais difícil")
  • Autômatos finitos / CFGs

Obviamente, há uma série de dificuldades nisso, mas todas deixam pelo menos algumas pessoas com um certo senso de 'surpresa', no sentido de que o problema pode parecer difícil, mas se torna tratável. O LP pode parecer relativamente simples, mas as pessoas demoraram um pouco para criar uma solução real. A repetição de quadrados ou a solução de 2-SAT é algo que um aluno de graduação pode inventar por conta própria, mas se você tivesse aprendido apenas sobre os problemas do NP-Complete sem ter visto o HORNSAT, isso poderia soar como um candidato natural à completude do NP. Resolver o CFSG ou ter uma maneira polinomial de verificar a redutibilidade do Delta-Wye não é uma proeza.

Espero que isto faça sentido; Obviamente, existem muitos atributos subjetivos aqui, mas estou curioso para saber o que outras pessoas consideram soluções eficientes para problemas "obviamente difíceis".

Alex Meiburg
fonte
Como motivação para esta pergunta (porque um amigo também estava perguntando): Frequentemente falamos sobre como é importante ensinar aos alunos sobre PN-Completude e Indecidibilidade, porque os ajuda a reconhecer quando os problemas serão muito difíceis e devem evitá-los. Esta lista seria 'problemas que você pode confundir com NP-Complete, mas você pode realmente resolver'. Não que eu espere muitos estudantes a plena sob a impressão de que os determinantes não pode ser computado - assim como eles provavelmente não vai encontrar 3SAT em estado selvagem - mas eles devem reconhecer outros problemas equivalentes
Alex Meiburg
1
Eu suspeito que isso seja amplo demais para ser um bom ajuste para o nosso site. Pedir uma lista exaustiva de algo não soa como o tipo de pergunta que funciona bem aqui. "Estou curioso para ouvir o que as outras pessoas acham ..." soa como o tipo de pergunta que não é adequada aqui; consulte o nosso centro de ajuda .
DW
1
Entendo, estava tentando reconhecer a subjetividade nessa questão, mas acho que essa questão é em grande parte algo que as pessoas concordariam e aprenderiam com discussões produtivas. Para perguntas com o tom que estou procurando , talvez (embora conheça um site diferente), consulte cstheory.stackexchange.com/questions/20930/… ou cstheory.stackexchange.com/questions/11119/… ?
Alex Meiburg
Além disso, não está claro o que "parece" exponencial a quem.
Raphael

Respostas:

2

Para mim, um dos algoritmos mais eficientes é o algoritmo Blossom V, que encontra a correspondência perfeita de peso máximo em um gráfico geral:

https://en.m.wikipedia.org/wiki/Blossom_algorithm

Dmitry Kamenetsky
fonte
1
Este é um bom exemplo! Não tendo realmente pensado ou precisado, acho que fiquei com a impressão de que a correspondência máxima em gráficos arbitrários era difícil para o NP. :)
Alex Meiburg
1

Para mim, todos os algoritmos clássicos e os mais eficientes, mais recentes , para verificar ou encontrar uma árvore de abrangência mínima (MST) de um gráfico com borda ponderada conectada são bons candidatos. Muitos desses algoritmos estão listados na wikipedia .

À primeira vista, esse problema parece o problema do vendedor ambulante, um dos poucos problemas mais difíceis de NP. Surpreendentemente, existem algoritmos lineares para verificar um MST e muitos algoritmos quase lineares para encontrar um MST! De fato, um dos problemas abertos mais famosos dos algoritmos é se existe um algoritmo linear determinístico para encontrar um MST em gráficos gerais. Acontece que existem estruturas e propriedades ricas em matemática e gráficos, além de uma infinidade de aplicativos práticos associados ao MST, tornando-o um dos tópicos mais agradáveis ​​e expansíveis no curso de ciência da computação. Para uma introdução abrangente um pouco desatualizada, mas muito bem escrita, consulte o tutorial de Jason Eisner .

John L.
fonte