¿Cuál es la diferencia entre "Decisión" y "Verificación" en la teoría de la complejidad?

En la Teoría de la computación de Michael Sipser en la página 270, escribe:

P = la clase de idiomas para los cuales la membresía se puede decidir rápidamente.
NP = la clase de idiomas para los cuales la membresía se puede verificar rápidamente.

¿Cuál es la diferencia entre "decidido" y "verificado"?

La tarea de decidir la membresía es: dada cualquier entrada , decidir si x ∈ L , es decir, calcular la siguiente función:$x$$x \in L$

$\qquad \displaystyle \chi_L(x) = \begin{cases}1 &x \in L \\ 0 & x\notin L\end{cases}$

Por otro lado, la tarea de verificar la membresía es: dada cualquier entrada una prueba (o testigo ) (propuesta ) de membresía, verifique rápidamente si x ∈ L con esa prueba ¹.$x$$x\in L$

Por ejemplo, considere la factorización prima. Dado , calcule todos los factores primos de n . Por otro lado, dado ( n , { i 1 , ... , i k } ) , verifique que ∏ k j = 1 i j = n . ¿Cuál es más fácil?$n \in \mathbb{N}$$n$$(n, \{i_1, \dots, i_k\})$$\prod_{j=1}^k i_j = n$

Otro ejemplo: dado un gráfico ponderado , decida si hay un círculo de Hamilton (que visita todos los nodos) con un peso máximo de k . Por otro lado, dado ( G , ( v 1 , … , v n ) ) , verifique si la ruta v 1 → ⋯ → v n visita todos los nodos exactamente una vez y tiene un peso máximo de k . ¿Qué es más difícil?$G = (V,E)$$k$$(G, (v_1, \dots, v_n))$$v_1 \to \dots \to v_n$$k$

1. Entonces dirá "no" si pero la prueba es incorrecta. Sin embargo, eso está bien, ya que consideramos máquinas no deterministas en este contexto; solo es importante que podamos adivinar la prueba correcta y verificarla (rápidamente).$x \in L$

Si ignoramos los problemas de eficiencia, hay otro ejemplo que ilustra la diferencia por analogía. Sabemos que el problema de detención no es decidible: dado un código para una máquina Turing, no hay una forma efectiva de determinar si la máquina se detiene si se ejecuta sin entrada.$e$

Pero si una máquina se detiene, no es difícil demostrarle a otra persona: solo dígales cuántos pasos ejecuta la máquina antes de detenerse. Pueden ejecutar la máquina durante tantos pasos y saber si usted dijo la verdad (ignorando la eficiencia, por supuesto).

Entonces, el conjunto de máquinas de Turing que se detienen no es decidible, pero es verificable. Tenga en cuenta que no se deben presentar pruebas para las máquinas que no se detienen. La verificación es asimétrica en el sentido de que solo la membresía en el conjunto tiene que ser verificable, la membresía fuera del conjunto no.

La situación con P y NP es análoga. Un lenguaje está en NP si hay un sistema de pruebas de manera que cada objeto que está en el idioma tenga una prueba corta (delimitada por un polinomio en el tamaño del objeto) que se puede verificar de manera eficiente (con una serie de pasos delimitados por un polinomio en el tamaño de la entrada).

Por otro lado, un lenguaje está en P si hay una manera de saber si un objeto arbitrario está o no en el lenguaje usando una serie de pasos delimitados por un polinomio en el tamaño del objeto. Ahora tenemos que preocuparnos por las entradas arbitrarias, no solo por los objetos en el lenguaje. Pero este problema es simétrico: si un lenguaje está en P, entonces también lo es su complemento. La pregunta de si el complemento de cada lenguaje NP es también un lenguaje NP no está resuelto.

(Esta analogía debe sugerir que los problemas de NP son para problemas de P, como los re conjuntos son para conjuntos computables. Eso es algo cierto, pero puede ser engañoso. Es un hecho básico que un conjunto que es re y co-re es computable, mientras que no se sabe si cada conjunto que es NP y Co-NP está en P).