## 3.2 VERIFICACIÓN DE T IEMPO POLINOMIAL

Dada una instancia del problema, una “solución” se puede verificar en tiempo polinomial. Ser polinomialmente verificable no implica tener una solución en tiempo polinomial.

Definición formal

NP= {L: existe un programa NDTM M que se ejecuta en tiempo polinomial para el cual LM = L}

El problema de decisión: π pertenece a NP bajo el esquema de codificación e si L [π, e] pertenece a NP.

Computación no determinista y la clase NP

La clase de complejidad NP consta de los problemas "verificables" en tiempo polinómico. Por verificable se entiende a un problema tal que dado un certificado de solución (candidato a solución), se puede verificar que dicho certificado es correcto en un tiempo polinómico en el tamaño de la entrada. A los problemas en la clase NP usualmente se les llama problemas NP.

El término NP proviene de no determinista en tiempo polinómico y se deriva de una caracterización alternativa de esta clase, donde se utilizan Máquinas de Turing no deterministas. Informalmente, se puede definir la clase NP en términos de un algoritmo no determinista.

El algoritmo mencionado está compuesto por 2 etapas separadas. Dada una instancia del problema I, la primera etapa simplemente "adivina" un candidato a solución S. Entonces, la etapa de verificación recibe como entrada a I y a S, y procede a realizar el cómputo de una manera determinista, finalmente deteniéndose con la respuesta "sí", o con la respuesta "no", o sigue computando sin detenerse.

Al igual que la clase P, la clase NP es insensible a la elección del modelo de cómputo no determinista, debido a que dichos modelos son equivalentes polinómicamente.

Clases de complejidad importantes

Muchas clases de complejidad importantes pueden ser definidas acotando el tiempo o el espacio utilizado por el algoritmo. Algunas de estas clases de problemas de decisión son:

Clase de complejidad | Modelo de cómputo | Restricción de recurso
DTIME(f(n)) | Máquina de Turing determinista | Tiempo f(n)
P | Máquina de Turing determinista | Tiempo poly(n)
EXPTIME | Máquina de Turing determinista | Tiempo 2poly(n)
NTIME(f(n)) | Máquina de Turing no determinista | Tiempo f(n)
NP | Máquina de Turing no determinista | Tiempo poly(n)
NEXPTIME | Máquina de Turing no determinista | Tiempo 2poly(n)
DSPACE(f(n)) | Máquina de Turing determinista | Espacio f(n)
L | Máquina de Turing determinista | Espacio O(log n)
PSPACE | Máquina de Turing determinista | Espacio poly(n)
EXPSPACE | Máquina de Turing determinista | Espacio 2poly(n)
NSPACE(f(n)) | Máquina de Turing no determinista | Espacio f(n)
NL | Máquina de Turing no determinista | Espacio O(log n)
NPSPACE | Máquina de Turing no determinista | Espacio poly(n)
NEXPSPACE | Máquina de Turing no determinista | Espacio 2poly(n)

###