¿Se puede mostrar la dureza NP mediante las reducciones de Turing?

En el artículo La complejidad del problema de Frobenius de Ramírez-Alfonsín, se demostró que un problema era NP completo usando reducciones de Turing. ¿Es eso posible? ¿Cómo exactamente? Pensé que esto solo era posible por un tiempo polinómico, muchas reducciones. ¿Hay alguna referencia sobre esto?

¿Hay dos nociones diferentes de dureza NP, incluso la integridad NP? Pero entonces estoy confundido, porque desde un punto de vista práctico, si quiero mostrar que mi problema es NP-hard, ¿qué uso?

Comenzaron la descripción de la siguiente manera:

Un tiempo polinómico La reducción de Turing de un problema a otro problema es un algoritmo A que resuelve utilizando una subrutina hipotética A 'para resolver modo que, si A' fuera un algoritmo de tiempo polinomial para entonces A sería un tiempo polinómico algoritmo para . Decimos que puede reducirse a Turing a . $P_1$ $P_2$ $P_1$ $P_2$ $P_2$ $P_1$ $P_1$ $P_2$

Un problema se llama (Turing) NP-hard si hay un problema de decisión NP-completo modo que puede reducirse a Turing a . $P_1$ $P_2$ $P_2$ $P_1$

Y luego usan una reducción de Turing de un problema de NP completo para mostrar la integridad de NP de algún otro problema.

complexity-theory time-complexity np-complete reductions usuario2145167
fuente

Respuestas:

Hay (al menos) dos nociones diferentes de dureza NP. La noción de costumbre, que utiliza la reducción de Karp, establece que un lenguaje es NP-difícil si todos los idiomas NP-Karp reduce a . Si cambiamos las reducciones de Karp a reducciones de Cook, obtenemos una noción diferente. Cada idioma que es Karp-NP-hard también es Cook-NP-hard, pero lo contrario es probablemente falso. Supongamos que NP es diferente de CONP, y tomar su favorito NP-completo lenguaje . Entonces, el complemento de es Cook-NP-hard pero no Karp-NP-hard. $L$ $L$ $L$ $L$

La razón por la que es Cook-NP-hard es la siguiente: tome cualquier lenguaje en NP. Desde es NP-duro, hay una función polytime tal que si y sólo si si y sólo si . Una reducción de Cook de a toma , calcula , verifica si $\overline{L}$ $M$ $L$ $f$ $x \in M$ $f(x) \in L$ $f(x) \notin \overline{L}$ $M$ $\overline{L}$ $x$ $f(x)$ , y da salida al inverso. $f(x) \in \overline{L}$

La razón por la que no es NP-hard (suponiendo que NP es diferente de coNP) es la siguiente. Supongamos que eran NP-hard. Luego, para cada lenguaje en coNP, hay una reducción de politiempo tal que iff , o en otras palabras, iff . Como está en NP, esto muestra que está en NP y, por lo tanto, coNP NP. Esto implica inmediatamente que NP coNP, y entonces NP = coNP. $\overline{L}$ $\overline{L}$ $M$ $f$ $x \in \overline{M}$ $f(x) \in \overline{L}$ $x \in M$ $f(x) \in L$ $L$ $M$ $\subseteq$ $\subseteq$

Si algún lenguaje Cook-NP-duro está en P, entonces P = NP: para cualquier lenguaje en NP, utilizan la reducción de Cook a para dar un algoritmo polytime para . Entonces, en ese sentido, los lenguajes completos de Cook-NP también son "más difíciles en NP". Por otro lado, es fácil ver que Cook-NP-hard = Cook-coNP-hard: una reducción de Cook para se puede convertir en una reducción de Cook para . Entonces perdemos algo de precisión al usar reducciones de Cook. $L$ $M$ $L$ $M$ $L$ $\overline{L}$

Probablemente haya otras deficiencias en el uso de reducciones de Cook, pero se lo dejaré a otros respondedores.

Yuval Filmus
fuente

Todavía no he entendido completamente todo esto, debo decir. Pero tengo otra pregunta, tal vez puedas responder esto (ya que no hay tantas otras respuestas): ¿qué pasa si tengo un rojo de Turing? desde el problema NP completo A hasta algún problema B y un rojo Karp. del problema B al problema C. ¿Establece eso la completitud NP del problema C (la membresía no es un problema)? Y en general, ¿puedo llamar al problema B NP-hard o más bien (Turing) NP-hard? ¡Gracias!

user2145167

Dos reducciones de Karp componen a una reducción de Karp, y dos reducciones de Cook componen a una reducción de Cook. Dado que una reducción de Karp también es una reducción de Cook, si compones una reducción de Karp y una reducción de Cook, obtienes una reducción de Cook. Pero en general no obtienes una reducción de Karp.

Yuval Filmus

x \in M

$x \in M$

f (x) \in L

$f(x) \in L$

f (x) \notin \bar{L}

$f(x) \notin \overline{L}$

A Karp-reducción de

es una función

(polytime en este caso) de tal manera que

si y sólo si

. Para cada siempre tiene que

M

$M$

L

$L$

f

$f$

x \in M

$x \in M$

f (x) \in L

$f(x) \in L$

f, x

$f,x$

f (x) \in L

$f(x) \in L$

f (x) \notin \bar{L}

$f(x) \notin \overline{L}$

\bar{L}

$\overline{L}$

L

$L$

f

$f$

Esta bien. Una reducción de Turing de tiempo polinomial es una reducción de Cook (como en el teorema de Cook-Levin) y la reducción de un problema de NP completo al nuevo problema da dureza de NP (al igual que una reducción de muchos polinomios de tiem, reducción de AKA Karp). De hecho, las reducciones de Karp son restricciones restringidas de Turing de todos modos.

Donde difieren (con respecto a esta pregunta) es en mostrar membresía. Una reducción de Karp de un problema a un problema en NP muestra que el primero está en NP. Una reducción de Cook en la misma dirección no lo hace.

Luke Mathieson
fuente

Gracias. Ni siquiera sabía que uno mostraba membresía explícitamente usando una reducción de Karp. Pero tiene sentido. Pero uno puede mostrar la membresía de NP usando reducciones de Turing en ambas direcciones, ¿verdad?

user2145167

@ user2145167 no, la respuesta de Yuval ofrece la historia completa aquí, pero en resumen, las reducciones de Cook son más débiles, así que permita más, por ejemplo, puede pasar de cualquier problema de co-NP a través de una reducción de Cook a cualquier problema de NP completo, que no es cierto para las reducciones de Karp.

Luke Mathieson el