Lo primero que hay que entender es que P y NP clasifican los lenguajes, no los problemas. Para entender lo que esto significa, primero necesitamos algunas otras definiciones.
Un alfabeto es un conjunto finito de símbolos no vacío.
{01} es un alfabeto es el conjunto de caracteres ASCII. {} no es un alfabeto porque está vacío. N (enteros) no es un alfabeto porque no es finito.
Sea Σ un alfabeto. Una concatenación ordenada de un número finito de símbolos de Σ se denomina palabra sobre Σ.
cadena 101 es una palabra sobre el alfabeto {01}. La palabra vacía (a menudo escrita como ε) es una palabra sobre cualquier alfabeto. La cadena penguin es una palabra sobre el alfabeto que contiene los caracteres ASCII. La notación decimal del número π no es una palabra sobre el alfabeto {.0123456789} porque no es finito.
La longitud de una palabra w, escrita como |w/, es el número de símbolos en ella.
Por ejemplo, |hello| = 5 y |ε| = 0. Para cualquier palabra w, / w / ∈ N y por lo tanto finito.
Sea Σ un alfabeto. El conjunto Σ contains contiene todas las palabras sobre Σ, incluyendo ε. El conjunto Σ + contiene todas las palabras sobre Σ, excluyendo ε. Para n ∈ N, Σn es el conjunto de palabras de longitud n.
Para cada alfabeto Σ, Σ＊ y Σ+ son conjuntos contables infinitos. Para el conjunto de caracteres ASCII ΣASCII, las expresiones regulares .* y .+ denotan ΣASCII respectively y ΣASCII+ respectivamente.
{01}7 es el conjunto de 7-bit ASCII códigos {00000000000001111111101}32 es el conjunto de valores enteros de 32 bits.
Sea Σ un alfabeto y L & subseteq; Σ＊. L se llama un lenguaje sobre Σ.
Para un alfabeto Σ, el conjunto vacío y Σ＊ son triviales idiomas sobre Σ. El primero se conoce a menudo como el lenguaje vacío. El lenguaje vacío {} y el lenguaje que contiene solo la palabra vacía {ε} son diferentes.
El subconjunto de {01} 32 que corresponde a valores de coma flotante no NaN IEEE 754 es un lenguaje finito.
Los idiomas pueden tener un número infinito de palabras, pero cada idioma es contable. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. El conjunto infinito de cadenas {23571113, …} denota el primer número en notación decimal es un subconjunto de los mismos. El lenguaje que contiene todas las palabras que coinciden con la expresión regular ?\d+\.\d*(?\d+)? es un lenguaje sobre el conjunto de caracteres ASCII (que denota un subconjunto de expresiones de coma flotante válidas definidas por el lenguaje de programación C).
No hay ningún lenguaje que contenga todos los números reales (en cualquier notación) porque el conjunto de números reales no es contable.
Sea Σ un alfabeto y L & subseteq; Σ＊. Una máquina D decide L si para cada entrada w ∈ Σ comp calcula la función característica xL (w) en tiempo finito. La función característica se define como
χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.Tal máquina se llama un decider para L. Escribimos » D (w) = x «para»dado w, D salidas x».
Hay muchos modelos de máquinas. La más general que está en uso práctico hoy en día es el modelo de una máquina de Turing. Una máquina de Turing tiene almacenamiento lineal ilimitado agrupado en celdas. Cada celda puede contener exactamente un símbolo de un alfabeto en cualquier momento. La máquina de Turing realiza su cálculo como una secuencia de pasos de cálculo. En cada paso, puede leer una celda, posiblemente sobrescribir su valor y mover el cabezal de lectura/escritura en una posición a la celda izquierda o derecha. La acción que realizará la máquina está controlada por un autómata de estado finito.
Una máquina de acceso aleatorio con un conjunto finito de instrucciones y almacenamiento ilimitado es otro modelo de máquina tan potente como el modelo de máquina de Turing.
Por el bien de esta discusión, no nos molestaremos con el modelo de máquina preciso que usamos, sino que bastará con decir que la máquina tiene una unidad de control determinista finita, almacenamiento ilimitado y realiza un cálculo como una secuencia de pasos que se pueden contar.
Dado que lo ha utilizado en su pregunta, asumo que ya está familiarizado con la notación «big-O», así que aquí solo hay un repaso rápido.
sea f: N → una función. El conjunto O(f) contiene todas las funciones g: N → N para las que existen constantes n0 ∈ N y c ∈ N tales que para cada n ∈ N con n > n0 es cierto que g(n) ≤ c f(n).
Ahora estamos preparados para abordar la pregunta real.
La clase P contiene todos los lenguajes L para los que existe una máquina de Turing D que decide L y una constante k ∈ N tal que para cada entrada w, D se detiene como máximo después de los pasos de T(|w|) para una función T ∈ O(n n nk).
Dado que O(n n nk), aunque matemáticamente correcto, es un inconveniente para escribir y leer, la mayoría de la gente, para ser honesto, todos excepto yo, generalmente escribe simplemente O (nk).
Tenga en cuenta que el enlace depende de la longitud de w. Por lo tanto, el argumento que haga para el lenguaje de los números primos solo es correcto para los números en codificaciones no regulares, donde para la codificación w de un número n, la longitud de la codificación |w| es proporcional a n. Nadie usaría tal codificación en la práctica. Usando un algoritmo más avanzado que simplemente probar todos los factores posibles, se puede demostrar, sin embargo, que el lenguaje de los números primos permanece en P si las entradas están codificadas en binario (o en cualquier otra base). (A pesar del gran interés, esto solo pudo ser probado por Manindra Agrawal, Neeraj Kayal y Nitin Saxena en un artículo galardonado en 2004, por lo que puede adivinar que el algoritmo no es muy simple.)
Los lenguajes triviales {} y Σ＊ y el lenguaje no trivial {ε} están obviamente en P (para cualquier alfabeto Σ). ¿Puede escribir funciones en su lenguaje de programación favorito que tomen una cadena como entrada y devuelvan un booleano que indique si la cadena es una palabra del lenguaje para cada una de ellas y demuestre que su función tiene complejidad polinómica en tiempo de ejecución?
Cada lenguaje regular (un lenguaje descrito por una expresión regular) en P.
Deje que Σ ser un alfabeto y L ⊆ Σ＊. Una máquina V que toma una tupla codificada de dos palabras w, c ∈ Σ＊ y produce 0 o 1 después de un número finito de pasos es un verificador para L si tiene las siguientes propiedades.
- Dado (w, c), V salidas de 1 sólo si w ∈ L.
- Para cada w ∈ L, existe un c ∈ Σ＊ tal que V(w, c) = 1.
La c en la definición anterior se denomina testigo (o certificado).
A un verificador se le permite dar falsos negativos para el testigo equivocado, incluso si w en realidad está en L. Sin embargo, no se le permite dar falsos positivos. También se requiere que por cada palabra en el idioma, exista al menos un testigo.
Para el COMPUESTO de lenguaje, que contiene las codificaciones decimales de todos los enteros que no son primos, un testigo podría ser una factorización. Por ejemplo, (659, 709) es un testimonio de 467231 ∈ COMPUESTO. Puede verificar fácilmente que en una hoja de papel sin el testigo dado, probar que 467231 no es primo sería difícil sin usar una computadora.
No dijimos nada sobre cómo se puede encontrar un testigo apropiado. Esta es la parte no determinista.
La clase NP contiene todos los lenguajes L para los que existe una máquina de Turing V que verifica L y una constante k ∈ N tal que para cada entrada (w, c), V se detiene después de como máximo los pasos de T(|w|) para una función T ∈ O(n n nk).
tenga en cuenta que la definición anterior implica que para cada w ∈ L existe un testigo c con |c| ≤ T(|w|). (La máquina de Turing no puede ver más símbolos del testigo.)
NP es un superconjunto de P (¿por qué?). No se sabe si existen lenguajes que estén en NP pero no en P.
La factorización de enteros no es un lenguaje per se. Sin embargo, podemos construir un lenguaje que represente el problema de decisión asociado con él. Es decir, un lenguaje que contiene todas las tuplas (n, m) de modo que n tiene un factor d con d ≤ m. Llamemos a este FACTOR de lenguaje. Si tiene un algoritmo para decidir el FACTOR, se puede usar para calcular una factorización completa con solo sobrecarga polinómica realizando una búsqueda binaria recursiva para cada factor primo.
Es fácil mostrar que el FACTOR está en NP. Un testigo apropiado sería simplemente el factor d en sí y todo lo que el verificador tendría que hacer es verificar que d ≤ m y n mod d = 0. Todo esto se puede hacer en tiempo polinómico. (Recuerde, de nuevo, que lo que cuenta es la longitud de la codificación y que es logarítmica en n)
Si puede demostrar que el FACTOR también está en P, puede estar seguro de obtener muchos premios geniales. (Y usted ha roto una parte significativa de la criptografía actual.)
Para cada lenguaje en NP, hay un algoritmo de fuerza bruta que lo decide de manera determinista. Simplemente realiza una búsqueda exhaustiva de todos los testigos. (Tenga en cuenta que la longitud máxima de un testigo está limitada por un polinomio. Por lo tanto, su algoritmo para decidir PRIMOS era en realidad un algoritmo de fuerza bruta para decidir COMPUESTO.
Para responder a su pregunta final, necesitamos introducir la reducción. Las reducciones son un concepto muy poderoso de la informática teórica. Reducir un problema a otro básicamente significa resolver un problema por medio de resolver otro problema.
Que Σ sea un alfabeto y A y B sean idiomas sobre Σ. A es tiempo polinómico múltiple reducible a B si existe una función f: Σ → → Σ Σ con las siguientes propiedades.
- w ∈ A f f (w) ∈ B para todo w ∈ Σ Σ.
- La función f puede ser calculada por una máquina de Turing para cada entrada w en un número de pasos delimitados por un polinomio en / w/.
En este caso, escribimos A ≤p B.
Por ejemplo, sea A el lenguaje que contiene todos los gráficos (codificados como matriz de adyacencia) que contienen un triángulo. (Un triángulo es un ciclo de longitud 3.) Sea B el lenguaje que contiene todas las matrices con traza distinta de cero. (La traza de una matriz es la suma de sus elementos diagonales principales.) Entonces A es tiempo polinómico múltiple reducible a B. Para probar esto, necesitamos encontrar una función de transformación apropiada f. En este caso, podemos establecer f para calcular la 3ª potencia de la matriz de adyacencia. Esto requiere dos productos matriz-matriz, cada uno de los cuales tiene complejidad polinómica.
Es trivialmente cierto que L ≤p L. (¿ Puede demostrarlo formalmente?)
Aplicaremos esto a NP ahora.
Un lenguaje L es NP-duro si y solo si L ‘≤p L para cada lenguaje L ‘ ∈ NP.
Un lenguaje NP-hard puede o no estar en NP mismo.
Un lenguaje L es NP-completo si y sólo si
- L ∈ NP y
- L es NP-duro.
El lenguaje completo NP más famoso es SAT. Contiene todas las fórmulas booleanas que se pueden satisfacer. Por ejemplo, (a ∨ b) ∧ (a ∨ b) ∈ SAT. Un testigo válido es {a = 1, b = 0}. La fórmula (a ∨ b) ∧ (a ∨ b) ∧ b ∉ SAT. (¿Cómo lo probarías?)
No es difícil demostrar que SAT ∈ NP. Mostrar la dureza NP del SAT es un trabajo, pero fue hecho en 1971 por Stephen Cook.
Una vez que se conocía un idioma NP completo, era relativamente sencillo mostrar el NP completo de otros idiomas a través de la reducción. Si se sabe que el lenguaje A es NP-duro, entonces mostrar que A ≤p B muestra que B es NP-duro, también (a través de la transitividad de «≤p»). En 1972 Richard Karp publicó una lista de 21 idiomas que pudo demostrar que eran NP-completo a través de la reducción (transitiva) del SAT. (Este es el único documento en esta respuesta que realmente recomiendo que lea. A diferencia de los demás, no es difícil de entender y da una muy buena idea de cómo funciona la comprobación de la integridad de NP a través de la reducción.)
por último, un breve resumen. Usaremos los símbolos NPH y NPC para denotar las clases de lenguajes NP-hard y NP-complete respectivamente.
- P ⊆ NP
- NPC &subconjunto; NP y NPC &subconjunto; NPH, en realidad NPC = NP N NPH por definición
- (A ∈ NP) ⇒ (B ∈ NPH) ⇒ A ≤p B
Tenga en cuenta que la inclusión NPC &subconjunto; NP es adecuada incluso en el caso de que P = NP. Para ver esto, aclare que ningún lenguaje no trivial puede reducirse a uno trivial y que hay lenguajes triviales en P, así como lenguajes no triviales en NP. Sin embargo, este es un caso de esquina (no muy interesante).
Su principal fuente de confusión parece ser que estaba pensando en la » n » en » O (n f f (n))» como la interpretación de la entrada de un algoritmo cuando en realidad se refiere a la longitud de la entrada. Esta es una distinción importante porque significa que la complejidad asintótica de un algoritmo depende de la codificación utilizada para la entrada.
Esta semana, se logró un nuevo récord para el Mersenne prime más grande conocido. El número primo más grande conocido actualmente es 274 207 281 − 1. Este número es tan grande que me da dolor de cabeza, así que usaré uno más pequeño en el siguiente ejemplo: 231 – 1 = 2 147 483 647. Se puede codificar de diferentes maneras.
- por su Mersenne exponente como número decimal:
31(2 bytes) - como número decimal:
2147483647(10 bytes) - como unario número:
11111…11donde…es reemplazado por 2 147 483 640 más1s (casi 2 GiB)
Todas estas cadenas codificar el mismo número y dado alguno de estos, se puede construir fácilmente cualquier otra codificación del mismo número. (Puede reemplazar la codificación decimal por binaria, octal o hexadecimal si lo desea. Solo cambia la longitud por un factor constante.)
El algoritmo ingenuo para probar la primalidad es solo un polinomio para codificaciones unarias. La prueba de primalidad de AKS es un polinomio para decimales (o cualquier otra base b ≥ 2). La prueba de primalidad de Lucas-Lehmer es el algoritmo más conocido para primos de Mersenne Mp con p un primo impar, pero sigue siendo exponencial en la longitud de la codificación binaria del exponente de Mersenne p (polinomio en p).
Si queremos hablar de la complejidad de un algoritmo, es muy importante que tengamos muy claro qué representación utilizamos. En general, se puede suponer que se utiliza la codificación más eficiente. Es decir, binario para enteros. (Tenga en cuenta que no todos los números primos son primos de Mersenne, por lo que usar el exponente de Mersenne no es un esquema de codificación general.)
En criptografía teórica, a muchos algoritmos se les pasa formalmente una cadena completamente inútil de k 1 s como primer parámetro. El algoritmo nunca mira este parámetro, pero permite que sea formalmente polinomio en k, que es el parámetro de seguridad utilizado para ajustar la seguridad del procedimiento.
Para algunos problemas para los que el lenguaje de decisión en codificación binaria es NP-completo, el lenguaje de decisión ya no es NP-completo si la codificación de los números incrustados se cambia a unario. Los idiomas de decisión para otros problemas siguen siendo NP-completos incluso entonces. Estos últimos se denominan fuertemente NP-completo. El ejemplo más conocido es el embalaje de contenedores.
También es (y quizás más) interesante ver cómo cambia la complejidad de un algoritmo si la entrada está comprimida. Para el ejemplo de los primos de Mersenne, hemos visto tres codificaciones, cada una de las cuales es logarítmicamente más comprimida que su predecesora.
En 1983, Hana Galperin y Avi Wigderson escribieron un artículo interesante sobre la complejidad de los algoritmos de grafos comunes cuando la codificación de entrada del grafo se comprime logarítmicamente. Para estas entradas, el lenguaje de los gráficos que contienen un triángulo desde arriba (donde estaba claramente en P) de repente se convierte en NP-completo.
Y esto se debe a que las clases de idiomas como P y NP están definidas para idiomas, no para problemas.