Consecuencias de problemas completos para NP cruza coNP

24

¿Cuáles son las consecuencias de tener problemas completos en ?NPcoNP

Marcos Villagra
fuente
Ver también mathoverflow.net/questions/34889/…
Jukka Suomela
Conozco ese enlace. Mi pregunta es sobre las consecuencias. Por ejemplo, si el lenguaje L está completo para entonces PH colapsa al nivel i , o algo así. NPcoNPi
Marcos Villagra
En realidad, hice la misma pregunta como comentario en ese enlace, pero quería que fuera una pregunta real.
Marcos Villagra
2
Sí, sé que lo sabes, pero la página de mathoverflow proporciona información de fondo útil para otros.
Jukka Suomela

Respuestas:

18

Este es un problema abierto (amplio); como en, no sabemos casi nada. Específicamente, debido a los trucos para probar los problemas completos de NPcoNP , necesitamos técnicas de prueba muy diferentes de las que existen actualmente. Como tal, una discusión de las consecuencias debería incluir razonablemente una tangente sobre "¿Qué significaría tener técnicas de prueba tan poderosas y nuevas?"

Para una discusión relativamente reciente sobre el tema, hay la columna 26 de NP-Completeness de David Johnson en las Transacciones de ACM en Algoritmos de 2007 ( PDF ). Permítanme parafrasear algo de lo que dice David con respecto a la cuestión de probar la existencia de problemas completos NPcoNP y agregar mis pensamientos:

Actualmente, solo tenemos candidatos naturales "débiles" para la membresía en NPcoNPP en el sentido de que la evidencia más sólida de su membresía es que aún no hemos logrado encontrar un algoritmo de tiempo polinómico para ellos. Enumera un par de candidatos: FACTOR PEQUEÑO, JUEGO STOCHASTIC SIMPLE y JUEGO DE PAGO MEDIO. Parte de la "rareza" adicional de estos problemas proviene de los mejores tiempos de ejecución heurísticos para resolverlos, por ejemplo, SMALL FACTOR, también conocido como INTEGER FACTOR k , tiene una complejidad de tiempo aleatorio de poly(n)2klog(k) . (Si existen problemas completos enNPcoNPP, entonces, ¿es eltiempo de ejecuciónsub-exponencial(ni puramente exponencial ni polinomial)endémico de la clase?)

Así específicamente, nos gustaría probar algo como: Un problema es sólo en P si y sólo si NPcoNP=P , es decir, un resultado completo como el teorema de Cook para 3SAT y NP . Para NP , tales pruebas implican universalmente reducciones de tiempo polinomial (y arreglan sus restricciones adicionales favoritas, por ejemplo, reducciones de Cook, reducciones de Karp). Como resultado, bajo las técnicas de reducción de tiempo polinomial, debe darse el caso de que exista una representación reconocible de la clase en tiempo polinomial. Para NP , podemos usar máquinas de Turing no deterministas que se detienen dentro de un polinomio, p(|x|) , número de pasos. Como señala David, tenemos representaciones similares para otras clases (donde el estado es más clara), tales comoPSPACE y#P .

Sin embargo, la dificultad de proporcionar una representación similar para NPcoNP es que el análogo "natural" nos permite incorporar el problema de detención dentro de la representación y, por lo tanto, es indecidible . Es decir, considere el siguiente intento de representar NPcoNP con dos máquinas de Turing no deterministas que, supuestamente, reconocen lenguajes complementarios:

Pregunta: ¿ Se detiene una máquina de Turing M on en la entrada x0,1n ?

Construya dos máquinas de Turing de tiempo lineal M1 y M2 siguiente manera. En la entrada y , M1 lee la entrada y siempre acepta. M2 siempre rechaza a menos que |y||x|y M acepta x en los pasos |y|.

M1M2 Mx

NPcoNPNPcoNP

NPcoNPNPcoNPNPcoNP

Daniel Apon
fuente
1
NPcoNPTFNP=F(NPcoNP)NPcoNP
Esto no se traduce directamente (en la forma en que creo que estás insinuando). Tenga en cuenta que el teorema no se refiere solo a CUALQUIER problema completo, sino a un problema completo de FNP. Esto es equivalente a decir "Hay un problema de NP completo en NP \ cap coNP iff NP = coNP". Hasta donde yo sé, es concebible que NP \ cap coNP tenga problemas completos que son distintos de los problemas NP-completos, sin colapso de PH . (Enlace es por diversión.))
Daniel Apon
Nota: Todavía se considera improbable que la situación que describí anteriormente como concebible sea el caso por las mismas razones en la respuesta.
Daniel Apon