En términos informales, NP es la clase de problemas de decisión para los que una solución propuesta dada, con una entrada dada se puede verificar rápidamente (en tiempo polinómico) para determinar si realmente es una solución (es decir, si satisface los requisitos del problema). Más formalmente, las entradas de un problema y las soluciones propuestas se deberán describir con cadenas de símbolos de algún conjunto finito, por ejemplo, el conjunto de caracteres del teclado de una terminal de computadora.

Necesitamos algunas convenciones para describir grafos, conjuntos, funciones, etc., que usan tales símbolos. El conjunto de convenciones que se adopta para un problema dado es la codificación de ese problema.

El tamaño de una cadena es el número de caracteres que contiene. Algunas cadenas de símbolos del conjunto escogido no son codificaciones válidas de objetos pertinentes al problema en cuestión; sólo son basura. En términos formales, una entrada de un problema y una solución propuesta para ese ejemplar del problema pueden ser cualquier cadena formada a partir del conjunto de caracteres.

La verificación de una solución propuesta incluye verificar que la cadena tenga sentido (es decir, que tenga la sintaxis correcta) como descripción del tipo de objeto requerido, además de verificar que satisfaga los criterios del problema. Por tanto, cualquier cadena de caracteres puede verse como un certificado para un ejemplar de un problema.
Podría haber problemas de decisión para los que no haya una interpretación natural de las "soluciones" o las "soluciones propuestas". En lo abstracto, un problema de decisión no es más que una función que relaciona un conjunto de cadenas de entrada con el conjunto {sí, no}. Una definición formal de NP considera todos los problemas de decisión y además, la definición emplea algoritmos no deterministas.

Ejercicios:

a) Determine si las siguientes afirmaciones son correctas o no.
1.- Si un problema es NP-completo, entonces no es posible resolverlo con ningún algoritmo en los peores casos.

2.- Si un problema es NP-completo, entonces no se ha descubierto ningún algoritmo polinomial para resolverlo en los peores casos.

3.- Si un problema es NP-completo, entonces es improbable encontrar en el futuro un algoritmo polinomial para resolverlo en los peores casos.

4.- Si un problema es NP-completo, entonces es improbable encontrar un algoritmo polinomial para resolverlo en los casos promedio.

5.- Si puede demostrarse que la cota inferior de un problema NP-completo es exponencial, entonces se ha demostrado que NP != P.

b) Determine la satisfactibilidad de cada uno de los siguientes conjuntos de cláusulas.

Conjunto 1.

-X, v -X2 v X3
X1
X2 v X3
-X3

Conjunto 2.
X1 vX2 v X3
-X1 v X2 v X3
X1 v -X2 v X3
X1 v X2 v -X3
-X1 v -X2 v X3

X1 v -X2 v -X3
-X1 v X2 v -X3
X1 v X2 v -X3
-X1 v -X2 v -X3

Conjunto 3.
-X1 v X2 v X3
-X1 v X2
X3

Conjunto 4.
X1 v X2 v X3
X1
X2

Conjunto 5.
-X1 v X2
-X2 v X3
-X3

c) Todos sabemos cómo demostrar que un problema es NP-completo. ¿Cómo puede demostrarse que un problema no es NP-completo?