¿Cuáles son las consecuencias de tener problemas completos en ?
cc.complexity-theory
conditional-results
Marcos Villagra
fuente
fuente
Respuestas:
Este es un problema abierto (amplio); como en, no sabemos casi nada. Específicamente, debido a los trucos para probar los problemas completos denortePAGS∩ c o NPAGS , 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 completosnortePAGS∩ c o NPAGS y agregar mis pensamientos:
Actualmente, solo tenemos candidatos naturales "débiles" para la membresía ennortePAGS∩ c o NPAGS- P 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 p o l y( n ) 2k l o g( k )√ . (Si existen problemas completos ennortePAGS∩ c o NPAGS- P , 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 enP si y sólo si NP∩coNP=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 paraNP∩coNP 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 NP∩coNP con dos máquinas de Turing no deterministas que, supuestamente, reconocen lenguajes complementarios:
Pregunta: ¿ Se detiene una máquina de TuringM∗ on en la entrada x∈0,1n ?
Construya dos máquinas de Turing de tiempo linealM1 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| .
fuente