Problemas com solução eficiente, exceto por uma pequena fração de entradas

18

O problema da parada para as máquinas de Turing é talvez o conjunto indecidível canônico. No entanto, provamos que existe um algoritmo que decide quase todas as instâncias dele. O problema da parada está, portanto, entre a crescente coleção daqueles que exibem o fenômeno da teoria da complexidade do “buraco negro”, pelo qual a dificuldade de um problema inviável ou indecidível se limita a uma região muito pequena, um buraco negro, fora do qual o problema está fácil.

[Joel David Hamkins e Alexei Miasnikov, " O problema da parada é decidível em um conjunto de probabilidade assintótica 1 ", 2005]

Alguém pode fornecer referências a outros "buracos negros" na teoria da complexidade ou a outro local em que esse ou outros conceitos relacionados são discutidos?

Jim Graber
fonte
3
Joel visita regularmente o MathOverflow, você pode fazer a pergunta aqui para obter uma resposta dele. IIRC houve uma pergunta sobre o resultado lá.
Kaveh
3
Veja também HeurP .
Kaveh
1
Talvez outro exemplo seja o isomorfismo do gráfico (que é um problema intermediário do NP). Em "instâncias reais" é muito fácil (trivial para instâncias aleatórias?) E para muitas classes de gráficos existe um algoritmo de tempo polinomial. O "buraco negro" parece tão rígido que não é tão fácil gerar instâncias difíceis, e o nauty, uma das ferramentas mais eficientes para resolvê- lo, é frequentemente usado para gerar instâncias (difíceis). Mas talvez o "buraco negro" desapareça e deixe o pobre soldado em P :-D
Marzio De Biasi 13/14
@Marzio, exemplos do mundo não real não costumam ser uma pequena fração de todas as instâncias e é diferente do que eles estão se referindo no artigo.
31
HeurP parece assumir uma distribuição de probabilidade em instâncias, mas acho que uma formalização diferente do fenômeno seria a seguinte: A linguagem é difícil para algumas classes, mas existe um problema promissor A = ( A y , A n ) que está em alguma classe mais fácil com A y "assintoticamente denso" em A e A n "assintoticamente denso" em ˉ A , onde assintoticamente é como o tamanho das strings nos idiomas vai para o infinito. UMAUMA=(UMAy,UMAn)UMAyUMAUMAnUMA¯
usul

Respostas:

15

Não tenho certeza se é isso que você procura, mas a transição de fase no SAT aleatório é um exemplo. Seja a razão entre o número de cláusulas e o número de variáveis. Então, uma instância aleatória do SAT com o parâmetro ρ provavelmente será satisfatória se ρ for menor que uma constante fixa (próximo a 4.2) e provavelmente não será satisfatória se ρ for um pouco mais do que essa constante. O "buraco negro" é a transição de fase.ρρρρ

Suresh Venkat
fonte
1
Semelhante a isso, pode-se mostrar que o Ciclo de Ham é polivolúvel em um gráfico aleatório (de acordo com algum processo razoável de geração aleatória), mas é NP-difícil apenas por causa de exemplos muito especialmente construídos. Existem muitos outros exemplos nessa linha.
JimN
5

Como o problema da parada, o problema da correspondência de Post é indecidível em geral. A tese de mestrado de Ling Zhao descreve um grande conjunto de instâncias solucionáveis ​​do problema do PCP, incluindo algumas instâncias "difíceis". Mas não sei se o tamanho / densidade / medida de seu conjunto de instâncias solucionáveis ​​está em pé de igualdade com o resultado do Problema de Halting que você cita.

http://webdocs.cs.ualberta.ca/~games/PCP/paper/CG2002.pdf

JimN
fonte