NP es la clase de lenguajes que tienen verificadores de tiempo polinómicos.
La clase NP, que significa "tiempo polinómico no determinista", es un concepto fundamental en la teoría de la complejidad computacional, un subcampo de la informática teórica. Para comprender la NP, primero hay que comprender la noción de problemas de decisión, que son preguntas con una respuesta de sí o no. Un lenguaje en este contexto se refiere a un conjunto de cadenas sobre algún alfabeto, donde cada cadena codifica una instancia de un problema de decisión.
Se dice que un idioma (L) está en NP si existe un verificador de tiempo polinomial para (L). Un verificador es un algoritmo determinista (V) que toma dos entradas: una instancia (x) y un certificado (y). El certificado (y) también se conoce como "testigo" o "prueba". El verificador (V) comprueba si el certificado (y) confirma que (x) pertenece a la lengua (L). Formalmente, un lenguaje (L) está en NP si existe un algoritmo de tiempo polinómico (V) y un polinomio (p(n)) tal que para cada cadena (x en L), existe una cadena (y) con ( |y| leq p(|x|)) y (V(x, y) = 1). A la inversa, para cada cadena (x en lugar de L), no existe ninguna cadena (y) tal que (V(x, y) = 1).
Para dilucidar este concepto, consideremos el conocido problema de la "satisfacibilidad booleana" (SAT). El problema SAT pregunta si existe una asignación de valores de verdad a variables en una fórmula booleana determinada de modo que la fórmula se evalúe como verdadera. El problema SAT está en NP porque, dada una fórmula booleana ( phi ) y una asignación ( alfa ) de valores de verdad a sus variables, se puede verificar en tiempo polinómico si ( alfa ) satisface ( phi ). Aquí, la instancia (x) es la fórmula booleana (phi) y el certificado (y) es la asignación (alpha). El verificador ( V ) verifica si ( alfa ) hace que ( phi ) sea verdadero, lo que se puede hacer en tiempo polinómico con respecto al tamaño de ( phi ).
Otro ejemplo ilustrativo es el problema del "camino hamiltoniano". Este problema pregunta si existe una ruta en un gráfico determinado que visite cada vértice exactamente una vez. El problema del camino hamiltoniano también está en NP porque, dado un gráfico ( G ) y una secuencia de vértices ( P ), se puede verificar en tiempo polinomial si ( P ) es un camino hamiltoniano en ( G ). En este caso, la instancia ( x ) es el gráfico ( G ) y el certificado ( y ) es la secuencia de vértices ( P ). El verificador ( V ) verifica si ( P ) forma una ruta hamiltoniana, lo que se puede hacer en tiempo polinomial con respecto al tamaño de ( G ).
El concepto de verificabilidad en tiempo polinomial es importante porque proporciona una manera de caracterizar problemas que se pueden verificar de manera eficiente, incluso si encontrar la solución podría ser computacionalmente inviable. Esto lleva a la famosa pregunta de si (P = NP), que pregunta si todo problema cuya solución se puede verificar en tiempo polinomial también se puede resolver en tiempo polinomial. La clase ( P ) consta de problemas de decisión que pueden resolverse en tiempo polinómico mediante una máquina de Turing determinista. Si ( P = NP ), significaría que cada problema con un verificador de tiempo polinomial también tiene un solucionador de tiempo polinomial. Esta cuestión sigue siendo uno de los problemas abiertos más importantes en informática.
Una de las propiedades clave de NP es que está cerrado bajo reducciones de tiempo polinomiales. Una reducción en tiempo polinomial de un lenguaje ( L_1 ) a un lenguaje ( L_2 ) es una función computable en tiempo polinomial ( f ) tal que ( x en L_1 ) si y solo si ( f(x) en L_2 ). Si existe una reducción de tiempo polinomial de (L_1) a (L_2) y (L_2) está en NP, entonces (L_1) también está en NP. Esta propiedad es fundamental en el estudio de la completitud de NP, que identifica los problemas "más difíciles" en NP. Un problema es NP-completo si está en NP y cada problema en NP puede reducirse a él en tiempo polinomial. El problema SAT fue el primer problema que demostró ser NP completo y sirve como base para demostrar la completitud NP de otros problemas.
Para ilustrar mejor el concepto de verificabilidad en tiempo polinomial, considere el problema de la "suma de subconjuntos". Este problema pregunta si existe un subconjunto de un conjunto dado de números enteros que sume un valor objetivo específico. El problema de la suma de subconjuntos está en NP porque, dado un conjunto de números enteros ( S ), un valor objetivo ( t ) y un subconjunto ( S' ) de ( S ), se puede verificar en tiempo polinomial si la suma de los elementos en (S') es igual a (t). Aquí, la instancia ( x ) es el par ( (S, t) ) y el certificado ( y ) es el subconjunto ( S' ). El verificador (V) comprueba si la suma de los elementos en (S') es igual a (t), lo que se puede hacer en tiempo polinómico con respecto al tamaño de (S).
La importancia de la verificabilidad en tiempo polinomial se extiende más allá de las consideraciones teóricas. En términos prácticos, significa que para los problemas en NP, si se proporciona una solución propuesta (certificado), se puede verificar de manera eficiente. Esto tiene implicaciones importantes para los protocolos criptográficos, los problemas de optimización y diversos campos en los que es importante verificar la exactitud de una solución.
En resumen, la clase NP abarca problemas de decisión para los cuales una solución propuesta puede verificarse en tiempo polinomial mediante un algoritmo determinista. Este concepto es fundamental en la teoría de la complejidad computacional y tiene profundas implicaciones para los aspectos teóricos y prácticos de la informática. El estudio de NP, la verificabilidad en tiempo polinomial y conceptos relacionados, como la integridad de NP, sigue siendo un área de investigación vibrante y crítica.
Otras preguntas y respuestas recientes sobre Complejidad: :
- ¿La clase PSPACE no es igual a la clase EXPSPACE?
- ¿Es la clase de complejidad P un subconjunto de la clase PSPACE?
- ¿Podemos demostrar que las clases Np y P son iguales encontrando una solución polinómica eficiente para cualquier problema NP completo en una TM determinista?
- ¿Puede la clase NP ser igual a la clase EXPTIME?
- ¿Hay problemas en PSPACE para los cuales no existe un algoritmo NP conocido?
- ¿Puede un problema SAT ser un problema NP completo?
- ¿Puede un problema estar en la clase de complejidad NP si hay una máquina de Turing no determinista que lo resolverá en tiempo polinomial?
- ¿P y NP son realmente la misma clase de complejidad?
- ¿Todos los lenguajes libres de contexto en la clase de complejidad P?
- ¿Existe una contradicción entre la definición de NP como una clase de problemas de decisión con verificadores de tiempo polinomial y el hecho de que los problemas de la clase P también tienen verificadores de tiempo polinomial?
Ver más preguntas y respuestas en Complejidad