¿Por qué la mayoría de las personas prefiere usar reducciones de muchos para definir la integridad de NP en lugar de, por ejemplo, reducciones de Turing?
39
¿Por qué la mayoría de las personas prefiere usar reducciones de muchos para definir la integridad de NP en lugar de, por ejemplo, reducciones de Turing?
Dos razones:
(1) solo una cuestión de minimidad: ser NPC bajo muchas reducciones es una declaración formalmente más fuerte y si obtienes la declaración más fuerte (como lo hizo Karp y como casi siempre lo haces), ¿por qué no decirlo?
(2) Hablar de reducciones de muchos da lugar a una jerarquía más rica y delicada. Por ejemplo, la distinción NP vs co-NP desaparece bajo las reducciones de Turing.
Esto es similar en espíritu a por qué a menudo se usan reducciones de Logspace en lugar de las de polytime.
No sé si hay una preferencia, pero se conjetura que son nociones distintas. Es decir, se supone que la reducibilidad de Turing es una noción más fuerte. (Existen A y B de tal manera que A es T-reducible a B, pero no más reducible a B.) Un artículo que discute esto es este de Lutz y Mayordomo. Proponen un fortalecimiento de la declaración P! = NP; aproximadamente, ese NP incluye una cantidad no despreciable de EXPTIME. Esta suposición les permite mostrar que las dos nociones de reducibilidad son distintas.
fuente
Creo que la razón por la que las personas prefieren (para empezar) las reducciones de muchos es pedagógica: una reducción de muchos de A a B es en realidad una función en las cuerdas, mientras que una reducción de Turing requiere la introducción de oráculos.
Tenga en cuenta que la reducción de Cook (tiempo de polinomio de Turing) y la reducción de Karp-Levin (tiempo de polinomio de muchos) se sabe que son distintas en E incondicionalmente, por Ko y Moore, y por separado por Watanabe (como se menciona en el artículo de Lutz y Mayordomo en la respuesta de Aaron Sterling).
fuente
Las reducciones de Turing son más poderosas que las reducciones de mapeo de muchos en este sentido: las reducciones de Turing le permiten asignar un idioma a su complemento. Como resultado, puede oscurecer la diferencia entre (por ejemplo) NP y coNP. En el artículo original de Cook, no examinó esta distinción (iirc Cook en realidad usaba fórmulas de DNF en lugar de CNF), pero probablemente se hizo evidente muy rápidamente que esta era una separación importante, y las reducciones de muchos hicieron que fuera más fácil lidiar con esto. .
fuente
para saltar un poco en otro ángulo / respuesta aquí por AS, esta es una pregunta abierta (también aquí ) en las fronteras de TCS si las reducciones de Cook ("Turing") son diferentes a las reducciones de Karp-Levin ("muchos-uno"), posiblemente equivalente a (¿clave principal?) preguntas abiertas de separaciones de clase de complejidad. aquí hay un nuevo resultado en este sentido
Separación de la integridad del cocinero de la integridad de Karp-Levin bajo una hipótesis / debasis de la peor dureza del caso Mandal, A. Pavan, Rajeswari Venugopalan (ECCC TR14-126)
fuente
En la teoría de la complejidad, también existe una noción de "jerarquía polinómica", aunque a diferencia de la jerarquía aritmética, solo se conjetura que existe. Esto lleva a clasificaciones que son más sutiles que "¿Es este problema tan difícil de resolver como NP?"
fuente
En general, la reducción Muchos-uno (Karp) es más fácil de diseñar porque es una forma restringida de reducción que hace una llamada y la tarea principal consiste en transformar la entrada en una codificación diferente. La reducción de Turing puede implicar una lógica compleja. La existencia de un conjunto completo para NP bajo la reducción de Turing pero no bajo la reducción de muchos implica que P! = NP.
Por ejemplo, la insatisfacción es completa para NP bajo reducción de Cook, pero no se sabe que sea completa para NP bajo reducción de Karp. Entonces, si demuestra que no hay una reducción de Karp de SAT a UNSAT (equivalente de UNSAT a SAT), entonces demostraría que NP! = CoNP y, por lo tanto, P! = NP.
fuente