Estoy tratando de entender (intuitivamente) los dos términos "capacidad de decisión" y "capacidad de verificación".
He realizado una cantidad razonable de búsqueda y revisión de los diversos textos que puedo tener en mis manos. Sin embargo, su comprensión intuitiva parece escapar de mí, especialmente para el segundo.
De las muchas definiciones encontradas, la siguiente que se encuentra en esta página , me explicó claramente la capacidad de decisión.
Un idioma se llama decidible si existe un método, cualquier método, para determinar si una palabra dada pertenece a ese idioma o no.
Sin embargo, no puedo encontrar una definición paralela de verificabilidad.
En el libro de Teoría de la Computación de Sipser , encontramos,
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.
A la luz de lo anterior, quiero entender la verificabilidad.
Proporcione tantos ejemplos como pueda, en un momento, trato de captar el significado, en el siguiente, me confundo nuevamente.
Respuestas:
La clave para entender aquí es que P y NP son clases de problemas de decisión. Eso significa que todos ellos tienen respuestas sí / no.
Entonces, cuando decimos que un problema como 3-SAT es NP-Completo, significa que dada una instancia de 3-SAT (también conocida como una palabra potencialmente en el idioma), no se conoce una manera eficiente de evaluar si la palabra es o no es en el idioma
Decir que algo está en NP significa que existe algún tipo de "prueba" para cada cadena en el lenguaje, que es polinomial en la longitud de la entrada.
Por ejemplo, en 3-SAT, estamos preguntando, ¿existe una asignación de Verdadero / Falso a un conjunto de variables en una fórmula booleana, de modo que la fórmula sea verdadera? La palabra que estamos probando es la fórmula booleana. No hay una forma conocida de encontrar si hay una solución única que haga que toda la fórmula sea verdadera. Pero, si tenemos un conjunto de valores verdadero / falso para las variables, es muy fácil verificar (en tiempo polinómico) si hace que la fórmula se evalúe como verdadera.
El punto clave aquí es que la palabra que estamos probando NO son los valores verdadero / falso para cada variable. La palabra que estamos probando es la fórmula que contiene las variables, y el lenguaje es el conjunto de todas las fórmulas booleanas que se evalúan como verdaderas.
No sabemos cómo evaluar de manera eficiente si la palabra (fórmula) está en el idioma (puede evaluar como verdadero), pero dado un conjunto de asignaciones verdadero / falso, podemos verificar si se evalúa como verdadero, es decir, es una "prueba "que la palabra (fórmula) está en el idioma. Por lo tanto, el problema está en NP, pero no se sabe que esté en P.
NP es en realidad la clase de problemas de decisión polinomiales no resolubles con solución. Esto se debe a que, en una máquina de turing no determinista, tenemos puntos de "decisión" en los que podemos tomar una de varias acciones, y nuestro certificador polinómico básicamente nos dice qué decisión tomar en cada punto de decisión.
fuente
supongamos que me da un problema y me pide una solución, así que digamos que puede verificar solo la cantidad polinómica de mi prueba (es decir: puede ejecutar un programa de computadora eficiente en mi prueba) cuando le envíe mi prueba de la solución todo lo que lo que debe hacer es ejecutar su programa y decidir de acuerdo con el resultado del programa.
por ejemplo: suponga que me pregunta si un gráfico es de 3 colores, entonces lo que tengo que hacer es enviar un color 3 del gráfico, luego verifica si todos los vértices adyacentes tienen colores diferentes, entonces el color es legal y el programa termina con "aceptar" (de lo contrario, la prueba no se acepta y terminamos con "rechazar").
eso se llama para verificar "rápidamente".
si puede construir un "programa de computadora" "eficiente" (o simplemente: algoritmo polinomial) que diga si una entrada (una cadena de longitud n) está en el lenguaje (o si la salida del programa 1 \ "acepta") esto es lo que quiero decir por clase de complejidad P.
ejemplo: supongamos que le doy una lista de cadenas (digamos la guía telefónica) y le pregunto sobre un nombre que debe decir si está en el libro o no. Una solución es lanzar todos los nombres y comparar cada nombre con el nombre dado, que dice que puede resolverlo en tiempo lineal.
otro ejemplo es: dado un gráfico G = (V, E) y un borde e = (u, v) y desea decir si el borde está en el gráfico.
fuente