¿Por qué los problemas de NPI no son todos de la misma complejidad?

¿Cómo se ve un problema y la razón por la que es probable NP-Intermedio en lugar de NP-Completo? A menudo es bastante simple observar un problema y determinar si es probable que esté NP-Completo o no, pero me parece mucho más difícil saber si un problema es NP-Intermedio ya que la línea parece ser bastante delgada entre los dos. clases Básicamente, lo que pregunto es por qué un problema que puede verificarse en tiempo polinomial (si es que lo hace) pero no resolverse en tiempo polinomial (siempre que P no sea igual a NP) no sería reducible entre sí en tiempo polinómico. Además, ¿hay alguna forma de mostrar que un problema es NP-Intermedio similar a cómo se muestra que un problema es NP-Duro, como la reducción o alguna otra técnica? También agradecería cualquier enlace o libro de texto que me ayudara a comprender la clase de NP-Intermedio.

cc.complexity-theory complexity-classes np-intermediate Jesse Stern
fuente

"un problema que puede satisfacerse en tiempo polinómico", supongo que quiere decir "un problema que puede verificarse en tiempo polinómico".

Kaveh

Hay una clase de problemas GI-completos que son polinomialmente equivalentes al isomorfismo de grafos. GI es un problema importante conjeturado como NP-intermedio

Mohammad Al-Turkistany

Por cierto, el título es engañoso, la igualdad de dos problemas de complejidad con respecto a una reducción (por ejemplo, reducciones de Karp) ya están definidos, sugeriría que lo cambie a algo como "¿Por qué los problemas de NPI no son todos de la misma complejidad?".

Kaveh

@kaveh Hizo todas las ediciones. Gracias por otra gran respuesta!

Jesse Stern

"A menudo es bastante simple observar un problema y determinar si es probable que sea NP-Completo o no". En mi humilde opinión, eso no podría estar más lejos de la verdad!

Mahdi Cheraghchi

Respuestas:

No se puede demostrar que un problema es sin separar de . $\mathsf{NPI}$ $\mathsf{P}$ $\mathsf{NP}$

Hay problemas artificiales que se pueden probar para estar en usando generalizaciones del teorema de Lander (ver también este ) suponiendo que . $\mathsf{NPI}$ $\mathsf{NP}\neq\mathsf{P}$

También versión acolchada de problemas son $\mathsf{NEXP\text{-}complete}$ $\mathsf{NPI}$ suponiendo (véase también esta y esta ). $\mathsf{NEXP} \neq \mathsf{EXP}$

A menudo se conjetura que un problema en es cuando: $\mathsf{NP}$ $\mathsf{NPI}$

podemos mostrar bajo suposiciones razonables que no es pero no se sabe que está en , $\mathsf{NPC}$ $\mathsf{P}$
podemos mostrar bajo suposiciones razonables que no está en pero no se sabe que está en , $\mathsf{P}$ $\mathsf{NPC}$

y en algún momento justo cuando no podemos mostrar que está en o . $\mathsf{NPC}$ $\mathsf{P}$

Un ejemplo de un supuesto razonable es la hipótesis del tiempo exponencial (o algunos de otros supuestos de dureza computacional ).

Básicamente, lo que pregunto es por qué un problema que puede satisfacerse en el tiempo polinómico (si es que lo hace) pero no se resuelve en el tiempo polinómico (siempre que P no sea igual a NP) no sería un tiempo polinómico reducible entre sí.

$\mathsf{NPC}\not \subseteq \mathsf{P}$ $\mathsf{P}$ $\mathsf{P}$ $\mathsf{NP}$

Kaveh
fuente

"2. podemos demostrar bajo suposiciones razonables que no está en P pero no se sabe que está en NP" ¿No quieres decir "... en NPC"?

Tyson Williams el

@Victor, no, no se sabe que no es igual a , y son diferentes si y son diferentes. Revertir tu edición.

P

$\mathsf{P}$

N P C

$\mathsf{NPC}$

P

$\mathsf{P}$

N P

$\mathsf{NP}$

Kaveh

@Kaveh, creo que estaba pensando en los idiomas triviales ( y ), pero que las excluyen de p

\emptyset

$\emptyset$

{0, 1}^{*}

$\{0,1\}^*$

didest

@ Diego, bueno, nada es reducible para ellos, pero tienes razón. Yo lo arreglare.

Kaveh

@Kaveh y Diego: Sí, estaba pensando en estos lenguajes triviales.

Victor Stafusa

Un caso típico es cuando un problema en también se encuentra en o . Suponiendo que la jerarquía polinómica no colapsa, este problema no puede ser -complete. Los ejemplos incluyen factorización de enteros, logaritmo discreto, isomorfismo gráfico, algunos problemas de red, etc. $\mathsf{NP}$ $\mathsf{coNP}$ $\mathsf{coAM}$ $\mathsf{NP}$

Mahdi Cheraghchi
fuente

Otro caso típico de problema de es cuando hay un testigo de longitud pero menor que . El problema de la existencia de una camarilla de tamaño en un gráfico es un ejemplo típico; en este caso, el testigo (la camarilla específica) requiere bits. $NPI$ $\omega(\log n)$ $n^{O(1)}$ $\log n$ $O(\log^2 n)$

Suponiendo la hipótesis del tiempo exponencial, este problema es más fácil que un completo de (que requiere tiempo ) pero más difícil que un problema de tiempo polinómico. $NP$ $\exp(n^{O(1)})$

David Harris
fuente