La forma estándar de demostrar que un problema es NP-completo es demostrar que otro problema conocido como NP-completo se reduce a él. Eso está claro. Dado un problema en NP, lo que se sabe es cómo demostrar que es no ¿NP-completo?
(Mi verdadera pregunta es probablemente inapropiada para este sitio por una o más razones; tengo curiosidad por saber cómo sería una prueba de que la factorización no es NP-completa).
Aquí está uno más puntero. Ladner del teorema establece que si $P \neq NP$, entonces hay un problema en $NP$ no $NP$-completa.
Richard E. Ladner: En la Estructura del Polinomio Tiempo de Reducibilidad. J. ACM 22(1): 155-171 (1975)
Por desgracia, las conocidas pruebas de este resultado producir bastante antinatural problema. El zombie-metafórico explicación es que usted tome la cabeza y el torso de un $NP$-conjunto completo y quirúrgicamente palo en los brazos y las piernas de un polinomio tiempo computable conjunto. (Si eso no es antinatural, no sé lo que es.)
Ver esta valoración crítica de dos pruebas.
Se conocen varios resultados en esta línea, todos los cuales utilizan una técnica: Se demuestra que si el problema es NP-completo, entonces falla alguna hipótesis de complejidad muy fuertemente creída. En las siguientes explicaciones, un asterisco* significa "a menos que una hipótesis de complejidad muy fuertemente creída (por ejemplo, P $\neq$ NP) falla".
Se sabe que la factorización no es NP-completa.* Hay que tener un poco de cuidado con la factorización por una razón técnica: en su versión más natural ("Dado un número, factorícelo") no es un "problema de decisión". Una versión estándar de problema de decisión es: "Dados n, L y U, ¿hay un factor primo de n entre L y U?". Esto se ve fácilmente que está en NP -- un testigo es simplemente un factor de n entre L y U. Por otro lado, este problema no es* NP-completo porque también está en coNP: hay un testigo que demuestra que n no tiene ningún factor primo entre L y U, es decir, una factorización prima de n. Así que si la factorización fuera NP-completa entonces todos los problemas en NP estarían en coNP; es decir, NP=coNP. Así que el asterisco en este párrafo se refiere a la suposición NP $\neq$ coNP, que se cree con mucha fuerza.
El problema del isomorfismo de los gráficos es un ejemplo más interesante. Decir si dos grafos dados son isomorfos está obviamente en NP (el testigo es el isomorfismo). Pero además, Graph- No isomorfismo también está "casi" en NP. En concreto, está en la clase AM, que es esencialmente "NP aleatorio". Existe una "prueba interactiva" aleatoria de ronda constante de que dos grafos no son isomorfos. (Básicamente, si pones los dos grafos a tus espaldas, los reetiquetas al azar, luego los muestras a un prover y el prover siempre puede decirte cuál es cuál, entonces te convences de que los grafos deben ser no isomorfos). De esto se deduce que el isomorfismo de grafos no es NP-completo, porque si lo fuera, el no isomorfismo de grafos sería coNP-completo, y entonces todos los problemas coNP estarían en AM. Y se sabe que esto implica que "la jerarquía de tiempo polinómico se colapsa" (el Teorema de Boppana-Hastad-Zachos), lo que se cree ampliamente que no sucede.
(Por cierto, supuse que te interesaban sobre todo los problemas que son(nB'yt tNhPe- cwoamyp,l eIt ea sbseucmaeuds ey otuh ewye raer em o(sptrleys uimnatbelrye)s tteodo iena spyr. o b lIenm st hteh aott haerre nd'itr eNcPt-icoonm,p ltehteer eb eacraeu sael stoh epyr oabrlee m(sp rtehsautm asbhloyu)l dtno'ot ebaes yN. P - cIonm ptlheet eo tbheecra udsier etchteiyo na,r et hteoroe haarred ;a les.og .p,r oblemas que no deberían ser NP-completos porque son demasiado difíciles; por ejemplo, $\Sigma_2$ -problemas completos como "Dada una fórmula de forma normal disyuntiva $\phi$ y un número $s$ ¿existe una fórmula DNF equivalente de tamaño máximo $s$ ?")
Hay versiones mucho más fuertes de la conjetura P vs. NP que los teóricos de la complejidad suelen tomar como axiomas, y que implican que muchos problemas no son NP-completos. La clase más estándar de supuestos es la conjetura de que la jerarquía NP no colapsa. Se puede definir NP como el análisis de juegos de solitario polinomialmente acotados con información completa. Por ejemplo, el Sudoku generalizado es un juego de este tipo y se sabe que es NP-completo. El enésimo nivel de la jerarquía polinómica $\Sigma^n P$ y $\Pi^n P$ puede definirse de forma similar mediante juegos con $n$ medio movimientos. Por ejemplo, supongamos que en el Sudoku generalizado, hay un tablero inicial, y primero puedo intentar hacerte perder rellenando algunas de las casillas, con restricciones. (Como, por ejemplo, sólo las casillas "rojas", y sólo con ciertos números.) Después de eso se puede mover. Entonces, si puedo ganar es un problema natural en $\Sigma^2 P$ .
En particular, la afirmación de que la jerarquía polinómica PH no colapsa implica que NP no es igual a co-NP. Si un problema está tanto en NP como en co-NP, no puede ser NP-completo sin colapso. (Prueba: Si el solitario fuera equivalente al cosolitario, entonces un juego con dos medias jugadas también sería equivalente al solitario). Un buen ejemplo cercano es el problema de isomorfismo de grafos, que está en NP y co-AM. AM es como NP pero con aleatoriedad; es el modelo en el que Arturo obtiene una prueba adaptativa en respuesta a una pregunta aleatoria y se convence estadísticamente. AM no es exactamente NP, pero se conjetura que es lo mismo. Así que si se juntan dos conjeturas estándar, el isomorfismo de grafos tampoco es NP-completo. Editar: Ryan y Harrison señalan que Boppana, Håstad y Zachos demostró que si NP está contenido en co-AM, entonces PH está contenido en $\Sigma^2 P$ . Es decir, la jerarquía se colapsaría en el segundo nivel tanto si AM = NP como si no. En particular, esto se aplica al isomorfismo de grafos.
Se sospecha fuertemente que los problemas de BQP, como la factorización, tampoco son NP-completos, pero es un problema abierto demostrar que eso implicaría que la jerarquía de polinomios se colapsa. Sin embargo, se sabe que los problemas basados en la decisión de la factorización, como por ejemplo si un número es libre de cuadrados, están tanto en NP como en co-NP. Esto ya se sabía antes, pero se deduce con especial rapidez del hecho de que la primalidad está en P, ya que eso certifica una factorización. Adenda: La certificación de la factorización equivale a certificación de primalidad que, como señaló David, fue demostrado por primera vez por Vaughan Pratt.
La única forma segura de demostrar que un problema de decisión no es NP-completo es probar que su respuesta es sí para todos los casos o no para todos los casos. Todo lo demás depende de la suposición de que P ≠ NP, porque si P = NP entonces todo problema de decisión no trivial es NP-duro.
Dicho esto, las formas estándar de convencer a los informáticos teóricos de que es poco probable que un problema sea NP-completo son encontrar un algoritmo de tiempo polinómico para él, o mostrar que el problema complementario pertenece a NP. Es famoso que para comprobar si un número es compuesto (claramente en NP: basta con mostrar una factorización), el artículo de Vaughan Pratt "Every prime has a succinct certificate" (SIAM J. Comput. 1975) mostró que era poco probable que fuera NP-completo mucho antes de que se demostrara que estaba en P.
En realidad, ahora que lo pienso, hay otra forma de demostrar que un problema no es NP-completo: demostrar que no está en NP, por ejemplo mostrando que es completo para una clase de complejidad superior como NEXP que se sabe que no colapsa a NP.
Bien, esto es lo que puede hacer, y esto lo voy a poner en una respuesta, porque es algo así como una respuesta. Si asumimos algo más fuerte que P \neq NP, como que la jerarquía de polinomios no colapsa, entonces podemos demostrar que algunas cosas no son NP-completas.
El mejor ejemplo de un resultado de este tipo (en realidad, es el primero en el que pensé, aunque en retrospectiva he visto los que otras personas mencionaron también) es que si el isomorfismo de grafos es NP-completo, la jerarquía polinómica colapsa al segundo nivel. No puedo encontrar una versión online del artículo en el que se demuestra esto (es de Boppana et al.) pero creo que el argumento es más o menos el siguiente: El isomorfismo de grafos está en NP, fácilmente. El isomorfismo de grafos también está en co-AM; si no sabes qué significa esto o no has visto la prueba, básicamente significa que si tienes dos grafos y te digo que son no isomorfo, puedes comprobar que digo la verdad probabilísticamente. Cómo: elige en secreto uno de los dos gráficos, permuta al azar sus vértices y envíamelo; yo te diré cuál es. Si los grafos son isomórficos, no podré darte la respuesta correcta más de la mitad de las veces, pero si no son isomórficos, siempre podré darte la respuesta correcta. (Estamos asumiendo aquí que tengo un poder computacional ilimitado).
Así que aplicamos un resultado de desandomización, para demostrar que el co-AM está contenido en algún nivel de la jerarquía de polinomios (creo que el segundo nivel), y entonces hemos terminado.
Que yo sepa, este es el único método que da este tipo de resultados condicionales. La razón por la que funciona es que PH es robusto contra cosas como la aleatoriedad, pero por supuesto tenemos que asumir conjeturas más fuertes en la teoría de la complejidad, así que definitivamente hay una compensación.
Aquí hay algo más que se me acaba de ocurrir: ¿Se sabe algo sobre lo que es una prueba condicional de que un determinado problema no es NP-duro no puede ¿se? (En la línea de la relativización, etc.) No es tan sencillo como la relativización, ya que todo lo que queremos es una prueba condicional, pero parece una pregunta interesante.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
