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

Para empezar, aquí tienes las definiciones superconcisas de las cuatro clases de complejidad en cuestión:

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

• NP es la clase de problemas de decisión que pueden ser resueltos en tiempo polinomial por una máquina de Turing no determinista. De manera equivalente, es la clase de problemas que pueden verificarse en tiempo polinomial por una máquina de Turing determinista.

• NP-hard es la clase de problemas de decisión a los que se pueden aplicar todos los problemas en NP reducido a en tiempo polinomial por una máquina de Turing determinista.

• NP-complete es la intersección de NP-hard y NP. De manera equivalente, NP-completo es la clase de problemas de decisión en NP a los que todos los demás problemas en NP pueden reducirse en tiempo polinomial mediante una máquina de Turing determinista.

Y aquí «sa 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 algún otro algoritmo B que resuelve el problema Y. Esta reducción se llama » reducción de tiempo polinomial «si todas las partes de A distintas de B tienen una complejidad de tiempo polinomial. Como ejemplo trivial, el problema de encontrar el elemento más pequeño en una matriz se puede reducir en tiempo constante al problema de clasificación, ya que puede ordenar la matriz y luego devolver el primer elemento de la matriz ordenada.

Uno Lo que es fácil pasar por alto en la definición NP-hard es que la reducción va de los problemas NP al problema NP-hard, pero no necesariamente al revés . Esto significa que los problemas NP-hard pueden ser en NP, o en una clase de complejidad mucho más alta (como puede ver en el diagrama de Euler), o es posible que ni siquiera sean problemas decidibles.Es por eso que la gente suele decir algo como «NP-hard significa al menos tan difícil como NP» cuando trata de explicar estas cosas de manera informal.

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

Es fácil demuestre que el problema de la detención es NP-duro pero no NP-completo. Por ejemplo, el problema de satisfacibilidad booleano se puede reducir al problema de la detención transformándolo en la descripción de una máquina de Turing que prueba 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 ciclo infinito. También es fácil ver que el problema de la 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 la detención, en general, es indecidible.

Comentarios

• @Nakano Intuitivamente, ‘ sa » reducción » en el sentido de que un problema se está convirtiendo en un subproblema de otro problema. El hecho de que algunas de estas reducciones aumenten la complejidad en lugar de disminuirla debido a una mala elección de » subproblem » simplemente significa que nunca usarías estas reducciones en cualquier código del mundo real. Aunque, para ser honesto, NP-hard me parece una clase extraña y no terriblemente interesante; puede ser más fructífero ignorarlo y pensar en NP-completo como el conjunto de problemas NP al que se reducen todos los demás problemas NP.
• @Nakano stackoverflow.com/questions/12637582/… Creo que la respuesta corta es que cuando la gente habla de que la factorización de enteros es NP, ‘ normalmente habla de números enteros realmente grandes, por lo que generalmente comienza a hacer sus pruebas de O grande con n como » el número de bits que el entero ocupa en la memoria » en lugar de » el número de enteros que pasó a la función «.
• @Nakano: en notación O grande, n es una medida del tamaño de la entrada (número de elementos, bytes, dígitos, etc.), no el valor del entrada.
• @Nakano La respuesta corta es que ‘ estás bien, y es por eso que cuando haces tiempo co análisis de complejidad siempre debe especificar qué significa n . La afirmación de que n es » el tamaño de la entrada » es simplemente un resumen conciso de cómo normalmente elegimos definir n. ‘ no es parte de las rigurosas definiciones de notación O grande o complejidad temporal. Creo que tiene razón al decir que la factorización de enteros es O (sqrt (n)) cuando n es el valor de la entrada. Da la casualidad de que los resultados de complejidad donde n significa tamaño suelen ser mucho más útiles en la práctica que aquellos donde n significa valor.
• @Nakano It ‘ También vale la pena tener en cuenta que técnicamente también debe definir la complejidad temporal de sus operaciones primitivas (suma, multiplicidad, lectura de memoria, escritura en memoria, comparación de dos números). La mayoría de las veces asumimos que todas estas primitivas son constantes o solo contamos un tipo de operación (por ejemplo, para los algoritmos de clasificación, tradicionalmente contamos las comparaciones). Sospecho que los resultados de la factorización de enteros no ‘ suponen que todas estas operaciones son de tiempo constante como solemos hacer, de lo contrario, el tamaño del número no ‘ no importa mucho.

La factorización de enteros 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.

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

Supongo que NP-Hard 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 así de 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 en absoluto

NP- Completo significa que un problema es NP y NP-Difícil. 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-Difícil).

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

No -el determinismo es una definición alternativa de NP. Una máquina de turing no determinista puede efectivamente duplicarse a sí misma en cualquier momento, y hacer que cada duplicado tome una ruta de ejecución diferente. Bajo esta definición, NP es el conjunto de problemas que pueden ser resueltos en tiempo polinomial por una computadora que puede duplicarse libremente. Resulta que este es exactamente el mismo conjunto de problemas que se pueden verificar en tiempo polinomial.

Comentarios

• Por lo tanto, es posible para $ O ( n ^ k) ¿$ algoritmos de tiempo serán problemas NP?
• k ¿es un número real constante? Si. Todos los problemas P son también problemas NP. Obviamente, cualquier cosa que pueda resolver en tiempo polinomial también se puede verificar en tiempo polinomial.
• ¿Cómo se define realmente la longitud / tamaño aquí? Por ejemplo, podría escribir $ n $ en una base grande y disminuir su longitud cuando se escriba. ¿Qué pasa con los problemas que no ‘ t tratan explícitamente con números enteros, pero dicen gráficos con $ V $ vértices y $ E $ bordes, etc.
• @Nakano, en realidad una base grande no ‘ t la cambiaría, porque solo sería una diferencia de factor constante. Por lo tanto, no tendría ‘ t un efecto polinomial frente a un no polinomio. Sin embargo, si escribiera el número en unario, entonces lo cambiaría.
• @Nakano, hmm … No ‘ me atrevería a tratar de explicar la complejidad clases para un niño de cinco años. : P

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

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

{0 , 1} es un alfabeto al igual que el conjunto de caracteres ASCII. {} no es un alfabeto porque está vacío. N (los números enteros) no es un alfabeto porque no es finito.

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

La cadena 101 es una palabra sobre el alfabeto {0, 1}. 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 {., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} porque no es finito.

El longitud de una palabra w , escrita como | w |, es el número de símbolos en él.

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

Sea Σ 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 infinitos conjuntos contables .Para el conjunto de caracteres ASCII Σ _ASCII , las expresiones regulares .* y .+ denota Σ _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.

Sea Σ un alfabeto y L ⊆ Σ ^＊ . L se denomina idioma sobre Σ .

Para un alfabeto Σ , el conjunto vacío y Σ ^＊ son lenguajes triviales sobre Σ . El primero se denomina a menudo 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 IEEE 754 no NaN 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,…} que denotan 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,…} que denota los números primos en notación decimal es un subconjunto adecuado del mismo. 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 válidas de punto flotante definidas por el lenguaje de programación C).

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

Let Σ ser un alfabeto y L ⊆ Σ ^＊ . Una máquina D decide L si por 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, otherwise.

Esta máquina se denomina decisor para L . Escribimos « D ( w ) = x » para «dado w , D salidas x ”.

Hay muchos modelos de máquina. El más general que se utiliza en la práctica 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 una posición hacia 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.

Por el bien de esta discusión, no nos molestaremos con el modelo de máquina preciso que usamos, sino que bastará decir que la máquina tiene una unidad de control determinista finita, almacenamiento ilimitado y realiza un cálculo como una secuencia de pasos eso se puede contar.

Ya que lo usó en su pregunta, supongo que ya está familiarizado con la notación “big-O” así que aquí hay solo un repaso rápido.

Sea f : N → ser una función.El conjunto O ( f ) contiene todas las funciones g : N → N para las que existen constantes n ₀ ∈ N y c ∈ N tal que por cada n ∈ N con n > n ₀ eso 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 T (| w |) pasos para una función T ∈ O ( n ↦ n ^k ).

Desde O ( n ↦ n ^k ), aunque matemáticamente correcto, es inconveniente para escribir y leer, la mayoría de la gente – para ser honesto, todos excepto yo – generalmente escribe simplemente O(n^k ).

Tenga en cuenta que el límite depende de la longitud de w . Por lo tanto, el argumento que presenta para el lenguaje de los números primos solo es correcto para números en codificaciones unaray , 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 interés masivo, esto solo pudo ser probado por Manindra Agrawal, Neeraj Kayal y Nitin Saxena en un documento 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 Σ ). ¿Puedes escribir funciones en tu 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 uno de ellos y demostrar que tu función tiene complejidad polinomial en tiempo de ejecución?

Todos los idiomas regulares (un idioma descrito por una expresión regular) están en P .

Sea Σ 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.

• Dadas ( w , c ), V genera 1 solo si w ∈ L .
• Para cada w ∈ L , hay existe un c ∈ Σ ^＊ tal que V ( w , c ) = 1.

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

Un verificador puede dar falsos negativos al testigo equivocado incluso si w realmente 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 idioma COMPOSITE, 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 testigo de 467231 ∈ COMPOSITE. Puede verificarlo fácilmente en una hoja de papel sin el testigo dado, demostrar que 467231 no es primo sería difícil sin usar una computadora.

No dijimos nada sobre cómo un testigo apropiado puede ser encontrado. Esta es la parte no determinista.

La clase NP contiene todos los idiomas L para los que existe una máquina de Turing V que verifica L y una constante k ∈ N tal que para cada input ( w , c ), V se detiene después de como máximo T (| w |) pasos 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 ver más símbolos del testigo).

NP es un superconjunto de P (¿por qué?). No se sabe si existen idiomas que están en NP pero no en P .

La factorización de enteros no es un idioma en sí. 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 del lenguaje. Si tiene un algoritmo para decidir FACTOR, puede usarlo para calcular una factorización completa con solo una sobrecarga polinomial realizando una búsqueda binaria recursiva para cada factor primo.

Es fácil mostrar que FACTOR está en NP . Un testigo apropiado sería simplemente el factor d mismo 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 polinomial. (Recuerde, nuevamente, que es la longitud de la codificación lo que cuenta y que es logarítmica en n .)

Si puede demostrar que FACTOR también está en P , puede estar seguro de que obtendrá muchos premios interesantes. (Y ha roto una parte importante de la criptografía actual).

Para cada idioma en NP , existe un algoritmo de fuerza bruta que decide es 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 COMPOSITE.

Para abordar su pregunta final, necesitamos introducir 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.

Sea Σ un alfabeto y A y B son idiomas sobre Σ . A es polinomio-tiempo muchos-uno reducible a B si existe una función f : Σ ^＊ → Σ ^＊ con las siguientes propiedades.

• w ∈ A   ⇔   f ( w ) ∈ B   para todos los 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 .

Para 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 además B el lenguaje que contiene todas las matrices con traza distinta de cero. (La traza de una matriz es la suma de sus principales elementos diagonales.) Entonces A es polinomio-tiempo muchos-uno reducible a B . Para probar esto, necesitamos encontrar una función de transformación apropiada f . En este caso, podemos configurar f para calcular la 3 ^rd potencia de la matriz de adyacencia. Esto requiere dos productos matriz-matriz, cada uno de los cuales tiene una complejidad polinomial.

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

Aplicaremos esto a NP ahora.

Un idioma L es NP -hard si y solo si L «≤ _p L para cada idioma L » ∈ NP .

Un NP lenguaje duro puede estar o no en NP .

Un idioma L es NP -complete 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 . Mostrar la dureza NP del SAT es un trabajo, pero lo hizo en 1971 Stephen Cook .

Una vez que se conoció un idioma NP completo, fue relativamente sencillo mostrar la completitud NP de otros idiomas mediante la reducción. Si se sabe que el idioma A es NP -hard, entonces se muestra que A ≤ _p B muestra que B también es NP -hard (a través de la transitividad de «≤ _p ”). En 1972, Richard Karp publicó una lista de 21 idiomas que podía mostrar que eran NP -completos mediante la reducción (transitiva) de SAT. (Este es el único documento de esta respuesta que de hecho le 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 prueba de NP -completo mediante reducción. )

Finalmente, un breve resumen. Usaremos los símbolos NPH y NPC para indicar las clases de NP -duro y NP -lenguajes completos 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 también hay lenguajes triviales en P como lenguajes no triviales en NP . Thi s es un caso de esquina (no muy interesante), sin embargo.

Apéndice

Su principal fuente de confusión parece ser que estaba pensando en el « 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, un nuevo récord para el Se logró Mersenne prime . El número primo más grande conocido actualmente 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. Se puede codificar de diferentes formas.

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

Todas estas cadenas codifican el mismo número y, dado cualquiera de ellas, podemos construir fácilmente cualquier otra codificación del mismo número (puede reemplazar la codificación decimal con binaria, octal o hexadeci mal si quieres. Solo cambia la longitud por un factor constante.)

El algoritmo ingenuo para probar la primalidad es solo polinomio para codificaciones unarias. La prueba de primalidad de 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 números primos de Mersenne M _p con p un primo impar pero aún es 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 asumir que se usa 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, muchos algoritmos pasan formalmente una cadena completamente inútil de k 1 s como primer parámetro. El algoritmo nunca analiza este parámetro, pero permite que sea 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 los 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 embalaje en contenedores .

También es (y quizás más) interesante ver cómo la complejidad de un algoritmo cambia si la entrada está comprimida . Para el ejemplo de los números 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 ha escrito un artículo interesante sobre la complejidad de los algoritmos 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 vuelve NP -completo.

Y eso «s porque las clases de idiomas como P y NP están definidas para idiomas , no para problemas .

Comentarios

• Esta respuesta probablemente no sea útil para el nivel de comprensión del autor de la pregunta. Lee las otras respuestas y observa con qué está luchando Nanako. ¿Crees que esto ¿La respuesta lo ayudará?
• Esta respuesta puede no ayudar a OP, pero ciertamente ayuda a otros lectores (incluido yo mismo).
• ¡Respuesta muy útil!

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

Problemas P: problemas que se pueden resolver en tiempo polinomial. Contiene problemas que se pueden resolver de manera eficiente.

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

Ahora, P vs NP en realidad pregunta si hay un problema cuya solución puede ser rápida comprobado que sea correcto, entonces siempre hay una forma rápida de resolverlo. Por tanto, escribiendo en términos matemáticos: ¿NP es un subconjunto de P o no?

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

NP difícil: los problemas que no se pueden verificar ni siquiera en el tiempo polinomial son np difíciles. Por ejemplo, elegir el mejor movimiento en el ajedrez es uno de ellos.

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

Espero que esto proporcione un contorno borroso.