¿La completitud de coNP implica dureza NP?

¿La completitud de coNP implica dureza NP? En particular, tengo un problema que he demostrado que es completo para coNP. ¿Puedo afirmar que es NP-hard? Me doy cuenta de que puedo reclamar dureza de coNP, pero no estoy seguro de si esa terminología es estándar.

Me siento cómodo con la afirmación de que si un problema de NP completo perteneciera a coNP, entonces NP = coNP. Sin embargo, estas notas de clase establecen que si un problema NP-duro pertenece a coNP, entonces NP = coNP. Esto sugeriría que no puedo afirmar que mi problema es NP-hard (o que he probado coNP = NP, lo cual dudo mucho).

Tal vez, hay algo mal con mi pensamiento. Mi pensamiento es que un problema completo de coNP es NP-hard porque:

cada problema en NP puede reducirse a su complemento, que pertenecerá a coNP.
el problema del complemento en coNP se reduce a mi problema de coNP completo.
por lo tanto, tenemos una reducción de cada problema en NP a mi coNP-complete, por lo que mi problema es NP-hard.

complexity-theory np-hard Austin Buchanan
fuente

en una palabra, no! al menos basado en el conocimiento actual. la pregunta está estrechamente relacionada con P =? NP (o más estrictamente coNP =? NP, que también está abierto). tenga en cuenta que si se prueba coNP ≠ NP, entonces P ≠ NP también se prueba porque P está cerrado bajo el complemento.

vzn

Respuestas:

Usted afirma que cada problema en NP puede reducirse a su complemento , y esto es cierto para las reducciones de Turing, pero (probablemente) no para reducciones de muchos. Una reducción de muchos de a es una función polytime tal que para todo , iff . $L_1$ $L_2$ $f$ $x$ $x \in L_1$ $f(x) \in L_2$

Si algún problema en CONP eran NP-duro, entonces para cualquier lenguaje no habría una función polytime tal que para todo , si y sólo si . Como está en coNP, esto proporciona un algoritmo de coNP para , que muestra que NP coNP, y por lo tanto NP coNP. La mayoría de los investigadores no esperan que este sea el caso, por lo que los problemas en coNP probablemente no sean NP-difíciles. $L$ $M \in NP$ $f$ $x$ $x \in M$ $f(x) \in L$ $L$ $M$ $\subseteq$ $=$

La razón por la que usamos las reducciones de Karp en lugar de las reducciones de Turing es para poder distinguir entre los problemas NP-hard y coNP-hard. Consulte esta respuesta para obtener más detalles (las reducciones de Turing se denominan reducciones de Cook en esa respuesta).

Finalmente, coNP-hard y coNP-complete son terminología estándar, y usted es libre de usarlas.

Yuval Filmus
fuente

NP \overset{?}{=} coNP

$\text{NP} \overset{?}{=} \text{coNP}$

co

$\text{co}$

NP

$\text{NP}$

Eso es correcto, y eso también es lo que muestro en la respuesta. Cuando dije que no es cierto para las reducciones de muchos, no lo dije en sentido estrictamente lógico, sino en el sentido de que "la reducción en la que estás pensando es una reducción de Turing pero no una reducción de muchos". .

Yuval Filmus

Oh, está bien, sí, ese es probablemente el problema.

G. Bach

Gracias. ¿Cuál es una buena referencia para esto? En particular para "NP = coNP bajo reducciones de Cook, pero se cree que son diferentes reducciones de wrt Karp"?

Austin Buchanan

La creencia de que NP es diferente de coNP está bastante extendida. A veces se le atribuye a Stephen Cook. Que la dureza NP es la misma que la dureza coNP bajo las reducciones de Cook se deduce inmediatamente de la definición.

Yuval Filmus

$x \in L$ $\text{M}$ $x \notin \overline{L}$ $\text{M}$ $x$ $NP$

$\text{NP}$ $\text{coNP}$ $L \in \text{coNP}$ $\text{M}$

x \in L ⟺ \forall z \in {0, 1}^{p (| x |)} : M (x, z) = 1

$x \in L \iff \forall z \in \{0,1\}^{p(|x|)}:\text{M}(x,z) = 1$

$\overline{L}$ $\text{M'}$

x \in \bar{L} ⟺ \exists z \in {0, 1}^{q (| x |)} : M' (x, z) = 1

$x \in \overline{L} \iff \exists z \in \{0,1\}^{q(|x|)}:\text{M'}(x,z) = 1$

$\text{NP}$ $\text{M'}$ $\text{K}$ $\text{coNP}$ $\text{M}$ $\text{K}$ $\forall$ $\text{coNP}$ $\text{NP}$ $\text{M'}$ $0$ $x \in \text{K}$ $\exists$ $\forall$

Tal vez de manera más abstracta: no está claro cómo construir (en tiempo polinómico) una máquina que reconozca exactamente los elementos de un idioma, independientemente de qué certificado venga con ellos, a partir de una máquina que reconozca exactamente los elementos de un idioma que tienen algún certificado para pero para el que tampoco funcionan algunos certificados.

G. Bach
fuente

Sorprendentemente, sin embargo, se sabe que NL = coNL, NPSPACE = coNPSPACE y, en general, las clases no deterministas definidas por restricciones de espacio están cerradas bajo complementación. Este es el teorema de Immerman-Szelepcsényi.

Yuval Filmus

Interesante, no lo sabía, pero la intuición detrás de esto probablemente es la forma en que siempre es con las clases espaciales: simplemente podemos reutilizar el espacio.

G. Bach

s

$s$

t

$t$

\log n

$\log n$

s

$s$

t

$t$