Necesito un ejemplo que muestre por qué SAT es un problema NP

Por favor, tengo dos preguntas:

(1) ¿Son NP-difícil, NP-problema y NP-Completo simplemente sinónimos?

(2) Entiendo que SAT es un problema NP que no se puede resolver en complejidad de tiempo polinomial. Solo me gustaría ver un ejemplo que muestre cómo SAT requiere tiempo exponencial en su lugar.

Gracias.

Estás equivocado sobre el significado de norte PAG - no se sabe si S A T se puede resolver en tiempo polinómico mediante una máquina de turing determinista. Pero si puede, entonces cada problema en norte PAG poder.
Pensé que SAT no era (NP) difícil.

Respuestas (1)

Parece que tienes los conceptos un poco confundidos. Arreglemos las cosas:

(1) No, las palabras NP-difícil, NP problema y NP-Completo no son sinónimos entre sí. NP es la clase de problemas que pueden resolverse mediante una máquina de Turing de tiempo polinomial no determinista.

Un problema es un problema NP si se encuentra en NP (es decir, si se puede resolver en poli-tiempo mediante una máquina de Turing no determinista).

Un problema es NP-difícil si todas las instancias de todos los demás problemas en NP se pueden traducir a instancias del mismo en tiempo polinomial determinista. Tenga en cuenta que un problema NP-difícil no tiene que estar en NP según esta definición.

Un problema es NP-completo si es tanto un problema NP como NP-difícil.

(2) Actualmente no se han encontrado ejemplos de instancias de SAT de tiempo exponencial, ni ninguna prueba de que tales ejemplos no existan. El punto central de la pregunta P = NP es si todos los problemas en NP (incluido SAT) pueden resolverse o no en tiempo polinomial determinista. Si hubiera una instancia de SAT en tiempo exponencial, esto habría resuelto inmediatamente el problema en forma negativa. En cuanto a si tal cosa existe o no, simplemente no lo sabemos hasta el momento.

Gracias .. Excelente y clara explicación :)
Gracias. Me esfuerzo por ser claro y completo en mi exposición :)
¿Puedo preguntarle a otro? Quiero ver un ejemplo para mostrar que SAT es un problema de NP. Solo para entender cómo se convierte en NP. GRACIAS
Tal vez esta podría haber sido su propia pregunta, pero está bien. El no determinismo es, intuitivamente, "suerte programada" en el sentido de que cada vez que hay que hacer una elección en el cálculo, siempre hacemos la correcta. (Otra forma de ver esto es introduciendo "testigos" que codifican las opciones, pero no tengo suficiente espacio para explicar) Para ver que SAT está en NP, tome una instancia de SAT. Podemos "elegir de manera no determinista" (hacer conjeturas afortunadas) si cada variable en la fórmula es verdadera o falsa. Adivinar y evaluar requiere tiempo polivalente y, al final, sabemos si la instancia fue satisfactoria. Entonces SAT está en NP.
(Adivinar y evaluar toma poli-tiempo, y al final sabemos si la instancia fue satisfactoria) lo que significa 2^n de otra manera!!! esto resume lo que quiero. GRACIAS
Necesito un ejemplo que muestre por qué SAT es un problema NP
RespuestasAquíPolítica de privacidad1y, 0v