El problema de detención para las máquinas de Turing es quizás el conjunto canónico indecidible. Sin embargo, demostramos que hay un algoritmo que decide casi todas las instancias del mismo. Por lo tanto, el problema de detención se encuentra entre la creciente colección de quienes exhiben el fenómeno del "agujero negro" de la teoría de la complejidad, por el cual la dificultad de un problema inviable o indecidible se limita a una región muy pequeña, un agujero negro, fuera del cual el problema es fácil.
[Joel David Hamkins y Alexei Miasnikov, " El problema de detención es decidible en un conjunto de probabilidad asintótica ", 2005]
¿Alguien puede proporcionar referencias a otros "agujeros negros" en la teoría de la complejidad, u otro lugar donde se discutan este o conceptos relacionados?
Respuestas:
fuente
Al igual que el problema de detención, el problema de correspondencia de Post es indecidible en general. La tesis de maestría de Ling Zhao describe un gran conjunto de instancias solucionables del problema de PCP, incluidas algunas instancias "difíciles". Pero no sé si el tamaño / densidad / medida de su conjunto de instancias solucionables está a la par con el resultado del Problema de detención que usted cita.
http://webdocs.cs.ualberta.ca/~games/PCP/paper/CG2002.pdf
fuente