Reducciones de muchos contra las reducciones de Turing para definir NPC

Respuestas:

32

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.

Noam
fuente
16
Si bien (2) es cierto, puedo usar (1) para argumentar que deberíamos usar reducciones uno a uno. Dado que la mayoría de las reducciones de muchos que construimos son de hecho reducciones de uno a uno, ¿por qué no las estudiamos cuando son formalmente más fuertes y las obtenemos la mayor parte del tiempo de todos modos? Creo que porque es más simple no tener que molestarse en probar la inyectividad, a pesar de que generalmente la tenemos. En ese sentido, quizás las reducciones de muchos son una especie de "reducciones de Ricitos de Oro": la potencia correcta, la simplicidad de prueba correcta.
Joshua Grochow
21

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.

Aaron Sterling
fuente
17

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).

Joshua Grochow
fuente
7

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. .

Kurt
fuente
11
Stephen Cook señaló durante su discurso de apertura en FLoC 2010 que su artículo de 1971 en realidad afirma demostrar que SAT está completo para P ^ NP bajo las reducciones de Turing ... Por supuesto, la formulación habitual se desprende de la misma prueba, por lo que esta es una situación de alguien reclamando menos de lo que demostraron! Consulte 4mhz.de/cook.html para obtener una versión reescrita del documento. Además, la oración "No hemos podido agregar {primos} o {pares de gráficos isomórficos} a [la lista de 4 problemas NP-completos]" siempre me hace sonreír.
András Salamon
5

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)

Mostramos que hay un lenguaje que está completo para Turing para NP pero no hay muchos completos para NP, bajo una hipótesis de dureza del peor de los casos .

vzn
fuente
4

Σ1Q

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?"

David Harris
fuente
3

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.

Mohammad Al-Turkistany
fuente
¿Puedes dar una referencia a tu última oración o explicarla?
Tayfun paga el
2
Le expliqué mi última oración.
Mohammad Al-Turkistany