Estoy tratando de entender estas clasificaciones y por qué existen. ¿Es correcto mi entendimiento? Si no, ¿qué?

1. P es la complejidad polinómica, o para algún número real no negativo , como , etc. Si un problema pertenece a P, entonces existe al menos un algoritmo que puede resolverlo desde cero en el tiempo polinómico. Por ejemplo, siempre puedo averiguar si algún número entero es primo haciendo un ciclo y comprobando en cada paso si se divide .O(nk)kO(1), O(n1/2), O(n2), O(n3)n2 <= k <= sqrt(n)kn

2. NP es una complejidad polinómica no determinista. Realmente no sé lo que significa que no sea determinista. Creo que significa que es fácil de verificar en tiempo polinómico, pero puede o no ser tiempo polinómico para resolver desde cero si aún no sabíamos la respuesta. Dado que puede resolverse en tiempo polinómico, todos los problemas de P también son problemas de NP. La factorización entera se cita como un ejemplo de NP, pero no entiendo por qué no es P, personalmente, ya que la factorización de prueba lleva O(sqrt(n))tiempo.

3. NP-Complete No entiendo nada, pero el problema del vendedor ambulante se cita como un ejemplo de esto. Pero en mi opinión, el problema de TSP podría ser NP, porque se necesita algo así como verificar si se le da el camino por adelantado.O(2n n2) time to solve, but O(n)

4. NP-Hard Supongo que está lleno de incógnitas. Difícil de verificar, difícil de resolver.

Básicamente tienes razón sobre P y NP, pero no sobre NP-hard y NP-complete.

Para empezar, aquí están las definiciones súper concisas de las cuatro clases de complejidad en cuestión:

• P es la clase de problemas de decisión que puede resolverse en tiempo polinómico mediante una máquina de Turing determinista.

• NP es la clase de problemas de decisión que puede resolverse en tiempo polinómico mediante una máquina de Turing no determinista. De manera equivalente, es la clase de problemas que puede verificarse en el tiempo polinómico mediante una máquina de Turing determinista.

• NP-hard es la clase de problemas de decisión a los que todos los problemas en NP pueden reducirse en tiempo polinómico mediante una máquina determinista de Turing.

• NP-complete es la intersección de NP-hard y NP. De manera equivalente, NP-complete es la clase de problemas de decisión en NP a la que una máquina determinista de Turing puede reducir todos los problemas en NP en tiempo polinómico.

Y aquí hay un diagrama de Euler de Wikipedia que muestra las relaciones entre estas cuatro clases (suponiendo que P no es igual a NP):

La parte con la que supongo que no está familiarizado o confundido es la noción de una "reducción de tiempo polinomial" del problema X al problema Y. Una reducción de X a Y es simplemente un algoritmo A que resuelve X haciendo uso de algunos otro algoritmo B que resuelve el problema Y. Esta reducción se denomina "reducción de tiempo polinomial" si todas las partes de A que no sean B tienen una complejidad de tiempo polinomial. Como ejemplo trivial, el problema de encontrar el elemento más pequeño en una matriz es reducible en tiempo constante al problema de clasificación, ya que puede ordenar la matriz y luego devolver el primer elemento de la matriz ordenada.

Una cosa que es fácil pasar por alto sobre la definición NP-hard es que la reducción va de los problemas NP al problema NP-hard, pero no necesariamente viceversa . Esto significa que los problemas difíciles de NP pueden estar en NP, o en una clase de complejidad mucho más alta (como puede ver en el diagrama de Euler), o incluso podrían no ser problemas decidibles. Es por eso que la gente suele decir algo como "NP-hard significa al menos tan duro como NP" cuando intenta explicar esto de manera informal.

El problema de detención es un buen ejemplo de un problema NP-hard que claramente no está en NP, como explica Wikipedia :

Es fácil demostrar que el problema de detención es NP-hard pero no NP-complete. Por ejemplo, el problema de satisfacción booleana puede reducirse al problema de detención transformándolo en la descripción de una máquina de Turing que intenta todas las asignaciones de valores de verdad y cuando encuentra una que satisface la fórmula, se detiene y, de lo contrario, entra en un bucle infinito. También es fácil ver que el problema de detención no está en NP ya que todos los problemas en NP son decidibles en un número finito de operaciones, mientras que el problema de detención, en general, es indecidible.

La factorización entera se cita como un ejemplo de NP, pero no entiendo por qué no es P, personalmente, ya que la factorización de prueba lleva tiempo O (sqrt (n)).

A los efectos de las clases de complejidad, nes la longitud de la entrada. Entonces, si desea factorizar un número entero k, nno es ksino log k, el número de bits (o lo que sea) que se necesita para anotar el número. Entonces, la factorización de enteros es O(sqrt(k))como usted dice, pero esto es lo que es .O(sqrt(2n))O(2(n/2))

NP-Hard Supongo que está lleno de incógnitas. Difícil de verificar, difícil de resolver.

No. NP-Hard se trata simplemente de cuán difícil es resolver un problema.

Los problemas NP-Hard son al menos difíciles como el problema más difícil en NP. Sabemos que son al menos tan difíciles, porque si tuviéramos un algoritmo de tiempo polinómico para un problema NP-Hard, podríamos adaptar ese algoritmo a cualquier problema en NP.

NP-Complete No entiendo nada

NP-Complete significa que un problema es NP y NP-Hard. Significa que podemos verificar una solución rápidamente (NP), pero es al menos tan difícil como el problema más difícil en NP (NP-Hard).

Realmente no sé lo que significa que no sea determinista.

El no determinismo es una definición alternativa de NP. Una máquina de turing no determinista es capaz de duplicarse efectivamente en cualquier momento y hacer que cada duplicado tome una ruta de ejecución diferente. Según esta definición, NP es el conjunto de problemas que una computadora puede resolver en tiempo polinómico y que puede duplicarse libremente. Resulta que este es exactamente el mismo conjunto de problemas que pueden verificarse en tiempo polinómico.

Lo primero que hay que entender es que P y NP clasifican lenguajes , no problemas . Para entender lo que esto significa, necesitamos algunas otras definiciones primero.

Un alfabeto es un conjunto finito no vacío de símbolos.

{ 0, 1} es un alfabeto como es el conjunto de caracteres ASCII. {} no es un alfabeto porque está vacío. N (los enteros) no es un alfabeto porque no es finito.

Deje Σ ser un alfabeto. Una concatenación ordenada de un número finito de símbolos de Σ se llama palabra sobre Σ .

La cadena 101es una palabra sobre el alfabeto { 0, 1}. La palabra vacía (a menudo escrita como ε ) es una palabra sobre cualquier alfabeto. La cadena penguines una palabra sobre el alfabeto que contiene los caracteres ASCII. La notación decimal del número π no es una palabra sobre el alfabeto { ., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} porque no es finito.

La longitud de una palabra w , escrita como | w |, es el número de símbolos que contiene.

Por ejemplo, | helloEl | = 5 y | ε | = 0. Para cualquier palabra w , | w | ∈ N y por lo tanto finito.

Deje Σ ser un alfabeto. El conjunto Σ ^＊ contiene todas las palabras sobre Σ , incluido ε . El conjunto Σ ⁺ contiene todas las palabras sobre Σ , excluyendo ε . Para 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 ^＊ y Σ _ASCII ⁺ respectivamente.

{ 0, 1} ⁷ es el conjunto de códigos ASCII de 7 bits { 0000000, 0000001..., 1111111}. { 0, 1} ³² es el conjunto de valores enteros de 32 bits.

Deje Σ ser un alfabeto y L ⊆ Σ ^＊ . L se llama lenguaje sobre Σ .

Para un alfabeto Σ , el conjunto vacío y Σ ^＊ son idiomas triviales sobre Σ . El primero a menudo se conoce como el lenguaje vacío . El idioma vacío {} y el idioma que contiene solo la palabra vacía { ε } son diferentes.

El subconjunto de { 0, 1} ³² que corresponde a valores de punto flotante no NaN IEEE 754 es un lenguaje finito.

Los idiomas pueden tener un número infinito de palabras, pero cada idioma es contable. El conjunto de cadenas { 1, 2, ...} denota los números enteros en notación decimal es un lenguaje infinito sobre el alfabeto { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. El conjunto infinito de cadenas { 2, 3, 5, 7, 11, 13, ...} denota los números primos en notación decimal es un subconjunto propio de los mismos. El lenguaje que contiene todas las palabras que coinciden con la expresión regular [+-]?\d+\.\d*([eE][+-]?\d+)?es un lenguaje sobre el conjunto de caracteres ASCII (que denota un subconjunto de las expresiones de coma flotante válidas según lo definido por el lenguaje de programación C).

No hay lenguaje que contenga todos los números reales (en cualquier notación) porque el conjunto de números reales no es contable.

Deje Σ ser un alfabeto y L ⊆ Σ ^＊ . Una máquina D decide L si para cada entrada w ∈ Σ ^＊ calcula la función característica χ _L ( w ) en tiempo finito. La función característica se define como

χ L : Σ ＊ → {0, 1}
     w   ↦ 1,   w ∈ L 
         0, de lo contrario.

Una máquina de este tipo se llama un decisivo para L . Escribimos " D ( w ) = x " para "dado w , D salidas x ".

Hay muchos modelos de máquinas. El más general que se usa actualmente en la práctica es el modelo de una máquina de Turing . Una máquina 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 que es tan poderoso como el modelo de máquina de Turing.

En aras de esta discusión, no nos molestaremos con el modelo de máquina preciso que usamos, sino que será suficiente 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.

Como lo ha usado en su pregunta, supongo que ya está familiarizado con la notación "big-O", así que aquí solo le ofrecemos un breve repaso.

Deje f : N → ser una función. El conjunto O ( f ) contiene todas las funciones g : N → N para las cuales existen constantes n ₀ ∈ N y c ∈ N de manera que por cada n ∈ N con n > n ₀ es cierto que g ( n ) ≤ c f ( n )

Ahora estamos preparados para abordar la verdadera pregunta.

La clase P contiene todos los lenguajes L para los cuales existe una máquina Turing D que decide L y una constante k ∈ N tal que para cada entrada w , D se detiene después de a lo sumo T (| w |) pasos para una función T ∈ O ( n ↦ n ^k ).

Dado que O ( n ↦ n ^k ), aunque matemáticamente correcto, es inconveniente para escribir y leer, la mayoría de las personas, para ser honesto, todos excepto yo, generalmente escriben simplemente O ( n ^k ).

Tenga en cuenta que el límite depende de la longitud de w . Por lo tanto, el argumento que hace para el lenguaje de los números primos solo es correcto para los números en codificaciones sin matriz , 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. Sin embargo, utilizando un algoritmo más avanzado que simplemente probando todos los factores posibles, se puede demostrar 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 idiomas 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 tome una cadena como entrada y devuelva un valor booleano que indique si la cadena es una palabra del lenguaje para cada una de ellas y demuestre que su función tiene una complejidad de tiempo de ejecución polinómica?

Cada regular de idioma (un lenguaje descrito por una expresión regular) está en P .

Deje Σ ser un alfabeto y L ⊆ Σ ^＊ . Una máquina V que toma una tupla codificada de dos palabras w , c ∈ Σ ^＊ y genera 0 o 1 después de un número finito de pasos es un verificador para L si tiene las siguientes propiedades.

• Dada ( w , c ), V salidas 1 sólo si w ∈ L .
• Para cada w ∈ L , existe una c ∈ Σ ^＊ tal que V ( w , c ) = 1.

La c en la definición anterior se llama testigo (o certificado ).

Se permite un verificador para dar falsos negativos para el testigo mal, incluso si w realidad está en L . Sin embargo, no está permitido dar falsos positivos. También se requiere que para cada palabra en el idioma, exista al menos un testigo.

Para el lenguaje COMPUESTO, 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 testigo de 467231∈ COMPOSITE. Puede verificarlo fácilmente en una hoja de papel sin contar con el testigo, demostrando 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 la mayoría de los pasos T (| w |) para una función T ∈ O ( n ↦ n ^k ).

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 mirar más símbolos del testigo).

NP es un superconjunto de P (¿por qué?). No se sabe si existen lenguas 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 idioma FACTOR. Si tiene un algoritmo para decidir FACTOR, se puede usar para calcular una factorización completa con solo una sobrecarga polinómica realizando una búsqueda binaria recursiva para cada factor primo.

Es fácil demostrar que FACTOR está en NP . Un testigo apropiado sería simplemente el factor d sí mismo y todo 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 eso es logarítmico en n .)

Si puede demostrar que FACTOR también está en P , puede estar seguro de obtener muchos premios geniales. (Y has roto una porción significativa de la criptografía de hoy).

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). Entonces, su algoritmo para decidir PRIMES fue en realidad un algoritmo de fuerza bruta para decidir COMPUESTO.

Para abordar 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 mediante la resolución de otro problema.

Deje Σ sea un alfabeto y A y B sea más idiomas Σ . A es polinomial en tiempo múltiple reducible a B si existe una función f : Σ ^＊ → Σ ^＊ con las siguientes propiedades.

• w ∈ A   ⇔   f ( w ) ∈ B   para todo w ∈ Σ ^＊ .
• La función f puede ser calculada por una máquina de Turing para cada entrada w en varios pasos delimitados por un polinomio en | w |.

En este caso, escribimos A ≤ _p B .

Por ejemplo, deje que A sea ​​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 más B el lenguaje que contiene todas las matrices con trazas distintas de cero. (La traza de una matriz es la suma de sus principales elementos de la diagonal.) Entonces A es de tiempo polinómico mucho-uno 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 ^rd poder de la matriz de adyacencia. Esto requiere dos productos de matriz de matriz, cada uno de los cuales tiene una complejidad polinómica.

Es trivialmente cierto que L ≤ _p L . (¿Puedes probarlo formalmente?)

Aplicaremos esto a NP ahora.

Un lenguaje L es NP- duro si y solo si L '≤ _p L para cada idioma L ' ∈ NP .

Un lenguaje duro NP puede o no estar en el propio NP .

Un lenguaje L es NP- completo si y solo 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 probarías eso?)

No es difícil demostrar que SAT ∈ NP . Para mostrar la dureza NP de SAT es un trabajo, pero fue realizado en 1971 por Stephen Cook .

Una vez que se conocía ese lenguaje completo NP , era relativamente simple mostrar la completitud NP de otros idiomas mediante reducción. Si se sabe que el lenguaje A es NP- duro, entonces mostrar que A ≤ _p B muestra que B también es NP- duro (a través de la transitividad de "≤ _p "). En 1972 Richard Karp publicó una lista de 21 idiomas que podía mostrar eran NP-completo a través de la reducción (transitiva) de SAT. (Este es el único artículo en esta respuesta que realmente recomiendo que lea. A diferencia de los otros, no es difícil de entender y da una muy buena idea de cómo funciona probar la completitud NP mediante la reducción).

Finalmente, un breve resumen. Usaremos los símbolos NPH y NPC para denotar las clases de los idiomas NP- hard y NP -complete respectivamente.

• P ⊆ NP
• NPC ⊂ NP y NPC ⊂ NPH , en realidad NPC = NP ∩ NPH por definición
• ( A ∈ NP ) ∧ ( B ∈ NPH ) ⇒   A ≤ _p B

Tenga en cuenta que la inclusión NPC ⊂ 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 idiomas triviales en P , así como idiomas no triviales en NP . Sin embargo, este es un caso de esquina (no muy interesante).

Apéndice

Su principal fuente de confusión parece ser que estaba pensando en la " n " en " O ( n ↦ 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 mayor premio Mersenne conocido . El número primo más grande actualmente conocido es 2 ^{74 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: 2 ³¹ - 1 = 2 147 483 647. Puede ser codificado de diferentes maneras.

• por su exponente de Mersenne como número decimal: 31(2 bytes)
• como número decimal: 2147483647(10 bytes)
• como número unario: 11111…11donde …será reemplazado por 2 147 483 640 más 1s (casi 2 GiB)

Todas estas cadenas codifican el mismo número y, dado cualquiera de estos, podemos construir fácilmente cualquier otra codificación del mismo número. (Si lo desea, puede reemplazar la codificación decimal por binaria, octal o hexadecimal. Solo cambia la longitud por un factor constante).

El algoritmo ingenuo para probar la primalidad es solo polinomial para codificaciones unarias. La prueba de primalidad AKS es polinomial para decimal (o cualquier otra base b ≥ 2). La prueba de primalidad de Lucas-Lehmer es el algoritmo más conocido para los primos de Mersenne M _p 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 sobre la complejidad de un algoritmo, es muy importante que tengamos muy claro qué representación usamos. 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 la criptografía teórica, a muchos algoritmos se les pasa formalmente una cadena de k 1 s completamente inútil como primer parámetro. El algoritmo nunca analiza este parámetro, pero le permite ser formalmente polinomial en k , que es el parámetro de seguridad utilizado para ajustar la seguridad del procedimiento.

Para algunos problemas para los cuales el lenguaje de decisión en la codificación binaria es NP- completo, el lenguaje de decisión ya no es NP- completo si la codificación de números incrustados se cambia a unario. Los lenguajes 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 se comprime . Para el ejemplo de los primos de Mersenne, hemos visto tres codificaciones, cada una de las cuales está 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 gráficos comunes cuando la codificación de entrada del gráfico 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 eso se debe a que las clases de idiomas como P y NP están definidas para idiomas , no para problemas .

Trataré de darle una definición menos informal para lo mismo.

Problemas P: problemas que pueden resolverse en tiempo polinómico. Contiene problemas que pueden resolverse eficientemente.

Problema NP: problemas que se pueden verificar en tiempo polinómico. Por ejemplo: vendedor ambulante, diseño de circuitos. Los problemas de NP son como acertijos (como sudoku). Dada una solución correcta para el problema, podemos verificar nuestra solución muy rápido, pero si realmente tratamos de resolverlo, podría llevarnos una eternidad.

Ahora, P vs NP realmente pregunta si un problema cuya solución se puede verificar rápidamente para que sea correcta, entonces siempre hay una forma rápida de resolverlo. Escribiendo así en términos matemáticos: ¿NP es un subconjunto de P o no?

Ahora volviendo a NP completo: estos son los problemas realmente difíciles de los problemas de NP. Por lo tanto, si hay una forma más rápida de resolver NP completo, NP completo se convierte en P y los problemas de NP colapsan en P.

NP difícil: los problemas que ni siquiera se pueden verificar en el tiempo polinómico son difíciles de resolver. Por ejemplo, elegir el mejor movimiento en el ajedrez es una de ellas.

Si algo no está claro, intente ver este video: https://www.youtube.com/watch?v=YX40hbAHx3s

Espero que esto proporcione un contorno borroso.