Para razonar sobre cosas como la completitud de NP, generalmente usamos muchas reducciones (es decir, reducciones de Karp). Esto lleva a imágenes como esta:
(bajo conjeturas estándar). Estoy seguro de que todos estamos familiarizados con este tipo de cosas.
¿Qué imagen obtenemos si trabajamos con reducciones de Turing (es decir, reducciones de Cook)? ¿Cómo cambia la imagen?
En particular, ¿cuáles son las clases de complejidad más importantes y cómo se relacionan? Supongo que juega el papel que solía y (porque está cerrado bajo las reducciones de Turing de la misma manera que está cerrado bajo las reducciones de Karp); es eso correcto? N P c o N P P N P N P
Entonces, ¿la imagen debería verse como ahora, es decir, algo así como lo siguiente?
¿Hay alguna secuencia nueva que desempeñe un papel que corresponda a la jerarquía polinómica? ¿Existe una secuencia natural de clases de complejidad , ,, ..., de modo que cada clase de complejidad se cierra bajo las reducciones de Turing? ¿Cuál es el "límite" de esta secuencia: es ? ¿Se espera que cada clase en la secuencia sea diferente de la anterior? (Por "esperado", quiero decir bajo conjeturas plausibles, similar al sentido en el que se espera que ).C 1 = P N P C 2 = ? P H P ≠ N P
Relacionado: reducciones de muchos contra las reducciones de Turing para definir NPC . Ese artículo explica que la razón por la que trabajamos con las reducciones de Karp es que nos da una jerarquía más precisa, más rica y más precisa. Esencialmente, me pregunto cómo sería la jerarquía si trabajáramos con las reducciones de Turing: cómo sería la jerarquía más gruesa, menos rica y menos precisa.
Respuestas:
Si la jerarquía polinómica no colapsa, todas las inclusiones son estrictas.
fuente