Suponiendo que P! = NP, creo que se ha demostrado que hay problemas que no están en P ni en NP-Complete. Se conjetura que el isomorfismo gráfico es un problema.
¿Hay alguna evidencia de más de esas 'capas' en NP? es decir, ¿una jerarquía de más de tres clases comenzando en P y culminando en NP, de modo que cada una sea un superconjunto apropiado de la otra?
¿Es posible que la jerarquía sea infinita?
cc.complexity-theory
Aryabhata
fuente
fuente
Respuestas:
¡Sí! De hecho, es probable que exista una jerarquía infinita de problemas cada vez más difíciles entre P y NP-completo bajo el supuesto de que P! = NP. Este es un corolario directo de la prueba del Teorema de Ladner (que estableció el no vacío de NP \ P)
Formalmente, sabemos que para cada conjunto S que no está en P, existe S 'no en P, de modo que S' es reducible por Karp a S pero S no es reducible por cocción a S '. Por lo tanto, si P! = NP, entonces existe una secuencia infinita de conjuntos S 1 , S 2 ... en NP \ P tal que S i + 1 es Karp-reducible a S i pero S i no es Cook-reducible a S i + 1 .
Es cierto que la gran mayoría de estos problemas son de naturaleza muy antinatural.
fuente
Existe una noción de "no determinismo limitado" que limita los bits no deterministas requeridos por la máquina Turing para llegar a una solución. La clase NP requiere, por ejemplo, O (n) bits. Al limitar los bits no deterministas a polylog, se define una jerarquía infinita de clases de complejidad llamada jerarquía \ beta P, todas con problemas completos propios.
Ver, por ejemplo, el siguiente artículo para más detalles: Goldsmith, Levy, Mundhenk, "No determinismo limitado", SIGACT News, vol 27 (2), páginas 20-29, 1996.
fuente