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?
Respostas:
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.ρ ρ ρ ρ
fonte
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
fonte