¿Cómo demostrar que un problema NO es NP-Complete?

17

¿Existe alguna técnica general para demostrar que un problema NO es NP-Complete?

Recibí esta pregunta en el examen que me pidió que mostrara si algún problema (ver más abajo) es NP-Complete. No se me ocurrió ninguna solución real, y solo probé que estaba en P. Obviamente, esta no es una respuesta real.

NP-Complete se define como el conjunto de problemas que se encuentran en NP, y todos los problemas de NP pueden reducirse a él. Por lo tanto, cualquier prueba debe contradecir al menos una de estas dos condiciones. Este problema específico, de hecho, está en P (y por lo tanto en NP). Así que estoy atascado con demostrar que hay algún problema en NP que no se puede reducir a este problema. ¿Cómo diablos se puede probar esto?

Aquí está el problema específico que me dieron en el examen:

Sea DNF el conjunto de cadenas en forma normal disyuntiva . Supongamos que DNFSAT es el lenguaje de cadenas de DNF que pueden satisfacerse mediante alguna asignación de variables. Muestre si DNFSAT está en NP-Completo.

Intitulado
fuente
8
Si se pudiera demostrar que DNF-SAT no es NP-completo, implicaría inmediatamente que , como ha demostrado. Por lo tanto, creo que la respuesta que estaban buscando es exactamente lo que usted dio (y probablemente se suponía que suponía implícitamente que P N P ). Aún así, esta es una pregunta muy engañosa. PNPPNP
Shaull
Tienes razón, así que entiendo que este problema es equivalente al problema de y una solución a uno, también resuelve el otro. P=NP
Sin título
¿Por qué dices de probar que DNFSAT está en P que "obviamente esta no es una respuesta real"?
András Salamon
55
@ AndrásSalamon Asume que , que es una declaración no probada. PNP
Sin título
1
@ Sin título: en realidad no asume P ≠ NP, vea mi respuesta.
András Salamon

Respuestas:

8

Según los comentarios, parece querer una respuesta incondicional.

Sin embargo, DNF-SAT está en L, asignando variables para satisfacer el primer disyuntivo. Por lo tanto, si es NP completo, entonces L = NP.

Por otro lado, si L = NP, entonces DNF-SAT es NP-completo bajo reducciones de espacio de registro, trivialmente. (De hecho, si L = NP, entonces cada problema en NP es NP completo bajo reducciones de espacio de registro).

Se deduce que L = NP si DNF-SAT es NP-completo bajo reducciones de espacio de registro.

Por lo tanto, actualmente no puede hacer una declaración incondicional de que DNF-SAT no tiene NP completo, como parece querer hacer. No es necesario asumir P ≠ NP, pero la respuesta tiene que estar condicionada a algo, y L ≠ NP es la hipótesis más débil posible que garantiza el resultado deseado.

András Salamon
fuente
Interesante. Así que este problema es equivalente al problema de . ¿Podría explicar por qué dice que L N P es una suposición débil? L=NP=P=NPCLNP
Sin título
3
Si entonces ψ es más débil que ϕ . ϕψψϕ
András Salamon
14

Un problema es NP-completo si es NP- duro y en NP. Esto significa que debe refutar uno de estos dos.Q

  1. Bajo el supuesto de que P NP, le puede dar una resolución de tiempo polinómico algoritmo Q . Más raramente, bajo el supuesto de que el isomorfismo gráfico no es NP-duro, puede mostrar que Q es politemporal reducible al isomorfismo gráfico.QQ
  2. Muestras que no está en NP. Esto es más difícil y, por lo general, debe usar otros supuestos, como el no colapso de la jerarquía polinómica, que NP coNP o mostrar que es difícil para alguna otra clase más alta que NP, por ejemplo, al demostrar que es NEXPTIME-hard.Q

Por lo general, la respuesta es dar un algoritmo de tiempo polinómico, que sería el más simple para DNF-SAT, pero esto se basa en la hipótesis de que P NP. Sin embargo, demostrar que DNF-SAT no es NP-completo sin ninguna suposición implica, como señala Shaull, probar que P NP, por lo que es algo más complicado.

Pål GD
fuente
1
Ambas técnicas que proporcionó se basan en algún tipo de suposición no probada. ¿Crees que podría haber una forma concreta (sin supuestos) de resolver un problema de este tipo?
Sin título
Ah, y no quise decir este problema específico, porque como dijo Shaull, este problema aún está abierto. Me refería a probar la integridad de coNP en general.
Sin título
2
@ Sin título Probablemente no se refería a la integridad de coNP. Una forma de mostrarlo es, en mi punto (2), demostrando que el problema es NEXPTIME-hard. Sabemos que NP NEXPTIME, así que eso lo probaría. Probar que un problema Q es NEXPTIME-hard, significaría que Q no puede estar en NP y, por lo tanto, no puede estar NP completo. QQ
Pål GD
10

Por la jerarquía de tiempo no determinista, podría mostrar que el problema es -hard; como N PN E X P , es imposible reducir el problema en tiempo polinómico a cualquier problema en N P , por lo que el problema no será en N P .NEXPNPNEXPNPNP

Sin embargo, si su problema no es tan difícil, es posible que tenga dificultades para demostrar que no está en ; y si esen N P , se le apuros para demostrar que N P no es Karp reducible a su problema sin suponer que PN P .NP NPNPPNP

Niel de Beaudrap
fuente
0

Como es el caso con todas las pruebas, no existe una fórmula para probar una declaración, debe hacer algunas conjeturas inteligentes, prueba y error y, con suerte, podrá probar lo que está tratando de probar. Para probar que un problema NO es NP-Complete, niegue la definición (Ley DeMorgran), es decir, pruebe que el problema NO está en NP o prueba el problema NO NP-Hard.

saadtaame
fuente
0

Creo que lo que el profesor realmente quiere es que puedas distinguir los problemas que están en P de los que tienen NP completo en el lenguaje de significado dado, ¿puedes construir un algoritmo eficiente? en caso afirmativo, se sospecha que no es NP-complete porque no creemos que los lenguajes en P sean NP-complete! de lo contrario, aún debe demostrar que el problema es NP-hard.

tenga en cuenta que existen algunos problemas que desconocemos, como el isomorfismo gráfico, la factorización de un número dado, ... ¡creemos que estos problemas no son NP completos, pero nadie puede probar eso! ¡específicamente tenemos evidencias de que el isomorfismo gráfico no es NP completo! Otro problema es la coyuntura única del juego que sospechamos que el juego único es NP-complete pero no existe ninguna prueba. ¡así que el enfoque que ha descrito no es útil!

fayez abd-alrzaq sordo
fuente