Pregunta ¿Cuáles son las diferencias entre NP, NP-Complete y NP-Hard?


¿Cuáles son las diferencias entre notario público, NP-Completo y NP-Hard?

Conozco muchos recursos en toda la web. Me gustaría leer tus explicaciones, y la razón es que podrían ser diferentes de lo que hay, o están ahí fuera y no lo sé.


906
2017-12-07 01:11


origen


Respuestas:


Supongo que está buscando definiciones intuitivas, ya que las definiciones técnicas requieren bastante tiempo para comprenderlas. Antes que nada, recordemos un concepto preliminar necesario para entender esas definiciones.

  • Problema de decisión: Un problema con un  o no responder.

Ahora, vamos a definir esos clases de complejidad.

PAG

P es una clase de complejidad que representa el conjunto de todos los problemas de decisión que se pueden resolver en tiempo polinomial.

Es decir, dado un ejemplo del problema, la respuesta sí o no se puede decidir en tiempo polinomial.

Ejemplo

Dado un gráfico conectado G, ¿pueden colorearse sus vértices utilizando dos colores para que ningún borde sea monocromático?

Algoritmo: comience con un vértice arbitrario, coloree el rojo y todos sus vecinos sean azules y continúe. Deténgase cuando se quede sin vértices o se vea forzado a hacer un borde; ambos extremos tendrán el mismo color.


notario público

NP es una clase de complejidad que representa el conjunto de todos los problemas de decisión para los cuales las instancias donde la respuesta es "sí" tienen pruebas que se pueden verificar en tiempo polinomial.

Esto significa que si alguien nos da una instancia del problema y un certificado (a veces llamado un testigo) para que la respuesta sea sí, podemos verificar que sea correcta en tiempo polinomial.

Ejemplo

Factorización de enteros está en NP. Este es el problema que da enteros n y m, ¿hay un número entero f con 1 < f < m, tal que f divide n (f es un pequeño factor de n)?

Este es un problema de decisión porque las respuestas son sí o no. Si alguien nos entrega una instancia del problema (entonces nos dan enteros) n y m) y un entero f con 1 < f < my afirmar que f es un factor de n (el certificado), podemos verificar la respuesta en tiempo polinomial realizando la división n / f.


NP-Completo

NP-Complete es una clase de complejidad que representa el conjunto de todos los problemas X en NP para lo cual es posible reducir cualquier otro problema NP Y a X en tiempo polinomial.

Intuitivamente esto significa que podemos resolver Y rápidamente si sabemos cómo resolver X con rapidez. Precisamente, Y es reducible a X, si hay un algoritmo de tiempo polinomial f para transformar instancias y de Y a las instancias x = f(y) de X en tiempo polinomial, con la propiedad de que la respuesta a y es sí, si y solo si la respuesta a f(y) Es sí.

Ejemplo 

3-SAT. Este es el problema en el que se nos da una conjunción (AND) de disyunciones (OR) de 3 cláusulas, declaraciones de la forma

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

donde cada x_vij es una variable booleana o la negación de una variable de una lista predefinida finita (x_1, x_2, ... x_n).

Se puede demostrar que cada problema de NP se puede reducir a 3-SAT. La prueba de esto es técnica y requiere el uso de la definición técnica de NP (basado en máquinas de Turing no deterministas) Esto se conoce como El teorema de Cook.

Lo que hace que los problemas de NP-complete sean importantes es que si se puede encontrar un algoritmo de tiempo polinomial determinista para resolver uno de ellos, cada problema de NP se puede resolver en tiempo polinomial (un problema para gobernarlos a todos).


NP-duro

Intuitivamente, estos son los problemas que son al menos tan difícil como los problemas NP-completos. Tenga en cuenta que los problemas NP-difícil no tiene que estar en NPy no tienen que ser problemas de decisión.

La definición precisa aquí es que un problema X es NP-hard, si hay un problema NP-completo Y, tal que Y es reducible a X en tiempo polinomial.

Pero dado que cualquier problema NP-completo se puede reducir a cualquier otro problema NP-completo en tiempo polinomial, todos los problemas NP-completos se pueden reducir a cualquier problema NP-difícil en tiempo polinomial. Entonces, si hay una solución para un problema NP-hard en tiempo polinomial, hay una solución para todos los problemas NP en tiempo polinomial.

Ejemplo

los detener el problema es un problema NP-difícil. Este es el problema que da un programa P y entrada I, se detendrá? Este es un problema de decisión, pero no está en NP. Está claro que cualquier problema NP-completo se puede reducir a este. Como otro ejemplo, cualquier problema NP-completo es NP-hard.

Mi problema NP-completo favorito es el Problema del Buscaminas.


P = NP

Este es el problema más famoso en informática, y una de las preguntas pendientes más importantes en las ciencias matemáticas. De hecho, el Clay Institute está ofreciendo un millón de dólares para una solución al problema (Stephen Cook writeup en el sitio web de Clay es bastante bueno).

Está claro que P es un subconjunto de NP. La pregunta abierta es si los problemas de NP tienen o no soluciones de tiempo polinomiales deterministas. Se cree en gran parte que no lo hacen. Aquí hay un artículo reciente sobresaliente sobre la última (y la importancia) del problema P = NP: El estado del problema P versus NP.

El mejor libro sobre el tema es Computadoras e intratable por Garey y Johnson.


1178
2017-12-07 01:46



He estado mirando alrededor y viendo muchas explicaciones largas. Aquí hay un pequeño cuadro que puede ser útil para resumir:

Observe cómo la dificultad aumenta de arriba abajo: cualquiera NP puede reducirse a NP-Completey cualquier NP-Complete se puede reducir a NP-Hard, todo en P (polinomio) tiempo.

Si puede resolver una clase de problema más difícil en tiempo P, eso significa que ha encontrado la manera de resolver todos los problemas más fáciles en tiempo P (por ejemplo, probar P = NP, si encuentra la manera de resolver cualquier problema NP-Completo en P tiempo).

____________________________________________________________
| Tipo de problema | Verificable en tiempo P | Soluble en tiempo P | Dificultad creciente
___________________________________________________________ | |
| P | Sí | Sí | |
| NP | Sí | Sí o No * | |
| NP-completo | Sí | Desconocido | |
| NP-Hard | Sí o No ** | Desconocido *** | |
____________________________________________________________ V

Notas sobre Yes o No entradas:

  • * Un problema NP que también es P puede resolverse en tiempo P.
  • ** Un problema NP-Hard que también es NP-Complete es verificable en tiempo P.
  • *** Pueden existir problemas de NP-Complete (todos los cuales forman un subconjunto de NP-hard). El resto de NP no lo es.

También encontré este diagrama bastante útil para ver cómo todos estos tipos se corresponden entre sí (preste más atención a la mitad izquierda del diagrama).


204
2017-10-22 06:08



Esta es una respuesta muy informal a la pregunta formulada.

¿Se puede escribir 3233 como el producto de otros dos números mayores que 1? ¿Hay alguna manera de recorrer un camino alrededor de todo el Siete puentes de Königsberg sin tomar ningún puente dos veces? Estos son ejemplos de preguntas que comparten un rasgo común. Puede no ser obvio cómo determinar la respuesta de manera eficiente, pero si la respuesta es 'sí', entonces hay una prueba corta y rápida para verificar. En el primer caso, una factorización no trivial de 51; en el segundo, una ruta para caminar los puentes (ajustando las restricciones).

UN problema de decisión es una colección de preguntas con respuestas afirmativas o negativas que varían solo en un parámetro. Diga el problema COMPOSITE = {"Is n compuesto": n es un entero} o EULERPATH = {"¿El gráfico G ¿Tienes un camino de Euler? ": G es un grafo finito}.

Ahora, algunos problemas de decisión se prestan a algoritmos eficientes, si no obvios. Euler descubrió un algoritmo eficiente para problemas como los "Siete Puentes de Königsberg" hace más de 250 años.

Por otro lado, para muchos problemas de decisión, no es obvio cómo obtener la respuesta, pero si conoce alguna información adicional, es obvio cómo probar que tiene la respuesta correcta. COMPUESTO es así: la división de prueba es el algoritmo obvio, y es lenta: para factorizar un número de 10 dígitos, debe intentar algo así como 100.000 posibles divisores. Pero si, por ejemplo, alguien le dijo que 61 es un divisor de 3233, la división larga simple es una forma eficiente de ver que están correctos.

La clase de complejidad notario público es la clase de problemas de decisión donde las respuestas 'sí' son cortas para indicar pruebas rápidas para verificarlas. Como COMPUESTO. Un punto importante es que esta definición no dice nada sobre cuán difícil es el problema. Si tiene una forma correcta y eficiente de resolver un problema de decisión, simplemente escribir los pasos en la solución es una prueba suficiente.

La investigación de algoritmos continúa y se crean nuevos algoritmos inteligentes todo el tiempo. Un problema que quizás no sepa cómo resolver eficientemente hoy puede resultar en una solución eficiente (si no obvia) mañana. De hecho, tomó investigadores hasta 2002 para encontrar una solución eficiente para COMPUESTO! Con todos estos avances, uno realmente tiene que preguntarse: ¿se trata de tener pruebas cortas solo como una ilusión? Tal vez cada El problema de decisión que se presta a pruebas eficientes tiene una solución eficiente? Nadie lo sabe.

Quizás la mayor contribución a este campo vino con el descubrimiento de una clase peculiar de problemas NP. Al jugar con los modelos de circuitos para computación, Stephen Cook encontró un problema de decisión de la variedad NP que era probablemente tan difícil o más difícil que cada otro problema NP Una solución eficiente para el problema de satisfacibilidad booleana podría usarse para crear una solución eficiente para cualquier otro problema en NP. Poco después, Richard Karp demostró que varios otros problemas de decisión podrían servir para el mismo propósito. Estos problemas, en cierto sentido los problemas "más difíciles" en NP, se conocen como NP-completo problemas.

Por supuesto, NP es solo una clase de problemas de decisión. Muchos problemas no se expresan naturalmente de esta manera: "encuentra los factores de N", "encuentra el camino más corto en el gráfico G que visita cada vértice", "da un conjunto de asignaciones de variables que hace que la siguiente expresión booleana sea verdadera". Aunque uno puede hablar informalmente acerca de que algunos de esos problemas están "en NP", técnicamente eso no tiene mucho sentido, no son problemas de decisión. Algunos de estos problemas pueden incluso tener el mismo tipo de poder que un problema NP completo: una solución eficiente a estos problemas (sin decisión) conduciría directamente a una solución eficiente a cualquier problema NP. Un problema como este se llama NP-duro.


70
2017-12-07 02:42



Además de las otras excelentes respuestas, aquí está el esquema típico la gente usa para mostrar la diferencia entre NP, NP-Complete y NP-Hard:

enter image description here


49
2017-11-24 17:50



La forma más fácil de explicar P v. NP y tal sin entrar en tecnicismos es comparar "problemas verbales" con "problemas de elección múltiple".

Cuando intentas resolver un "problema verbal", debes encontrar la solución desde cero. Cuando intentas resolver un "problema de elección múltiple", tienes una opción: o resuélvelo como lo harías con un "problema verbal", o trata de tapar cada una de las respuestas que se te dieron, y elige la respuesta que corresponda.

A menudo sucede que un "problema de elección múltiple" es mucho más fácil que el correspondiente "problema verbal": sustituir las respuestas candidatas y verificar si encajan puede requerir un esfuerzo significativamente menor que encontrar la respuesta correcta desde cero.

Ahora bien, si aceptamos el esfuerzo que lleva al tiempo polinomial "fácil", entonces la clase P consistiría en "problemas verbales fáciles", y la clase NP consistiría en "problemas fáciles de elección múltiple".

La esencia de P v. NP es la pregunta: "¿Hay algún problema fácil de elección múltiple que no sea fácil como un problema verbal"? Es decir, ¿hay problemas para los cuales es fácil verificar la validez de una respuesta dada, pero encontrar esa respuesta desde cero es difícil?

Ahora que entendemos intuitivamente qué es NP, tenemos que desafiar nuestra intuición. Resulta que hay "problemas de elección múltiple" que, en cierto sentido, son los más difíciles de todos: si uno encuentra una solución a uno de esos problemas "más difíciles de todos" uno podría encontrar una solución para TODOS Problemas de NP! Cuando Cook descubrió esto hace 40 años, fue una completa sorpresa. Estos problemas "más difíciles de todos" se conocen como NP-hard. Si encuentra una "solución de problemas de palabras" para uno de ellos, automáticamente encontrará una "solución de problemas de palabras" para cada uno de los "problemas fáciles de elección múltiple".

Finalmente, los problemas NP-completos son aquellos que son simultáneamente NP y NP-hard. Siguiendo nuestra analogía, son a la vez "fáciles como problemas de elección múltiple" y "los más difíciles de todos como problemas verbales".


40
2017-08-08 20:41



P (Tiempo polinomial): como su propio nombre indica, estos son los problemas que pueden resolverse en tiempo polinomial.

NP (Tiempo no determinista-polinomial): estos son los problemas de decisión que pueden verificarse en tiempo polinomial. Eso significa que si afirmo que hay una solución de tiempo polinomial para un problema en particular, me pides que lo demuestre. Luego, le daré una prueba que puede verificar fácilmente en tiempo polinomial. Este tipo de problemas se llaman problemas NP. Tenga en cuenta que, aquí no estamos hablando de si hay una solución de tiempo polinomial para este problema o no. Pero estamos hablando de verificar la solución a un problema dado en tiempo polinomial.

NP-Hard: Estos son al menos tan difíciles como los problemas más difíciles en NP. Si podemos resolver estos problemas en tiempo polinomial, podemos resolver cualquier problema NP que pueda existir. Tenga en cuenta que estos problemas no son necesariamente problemas de NP. Eso significa que podemos / no podemos verificar la solución a estos problemas en tiempo polinomial.

NP-Complete: estos son los problemas que son NP y NP-Hard. Eso significa que, si podemos resolver estos problemas, podemos resolver cualquier otro problema de NP y las soluciones a estos problemas se pueden verificar en tiempo polinomial.


34
2017-10-04 03:50



Creo que podemos responderlo de manera más sucinta. Yo respondí una pregunta relacionaday copiando mi respuesta desde allí

Pero primero, un problema NP-hard es un problema por el cual no podemos probar que existe una solución de tiempo polinomial. La dureza NP de algún "problema-P" generalmente se prueba convirtiendo un problema NP-hard ya probado al "problema-P" en tiempo polinomial.

Para responder el resto de la pregunta, primero debe comprender qué problemas NP-hard también son NP-completos. Si un problema NP-duro pertenece al conjunto NP, entonces es NP-completo. Para pertenecer al conjunto NP, un problema debe ser

(i) un problema de decisión,
  (ii) el número de soluciones al problema debe ser finito y cada solución debe ser de longitud polinómica, y
(iii) dada una solución de longitud polinómica, deberíamos poder decir si la respuesta al problema es sí / no

Ahora, es fácil ver que podría haber muchos problemas NP-hard que no pertenecen al conjunto NP y son más difíciles de resolver. Como un ejemplo intuitivo, la versión de optimización del vendedor ambulante donde necesitamos encontrar un cronograma real es más difícil que la versión de decisión del vendedor ambulante, donde solo tenemos que determinar si existe un cronograma con una longitud <= k o no.


16
2018-06-18 16:52



Los problemas NP-completos son aquellos que son NP-Hard y en la clase de complejidad NP. Por lo tanto, para mostrar que un problema determinado es NP-completo, debe mostrar que el problema está en NP y que es NP-hard.

Los problemas que están en la clase de complejidad NP pueden resolverse de manera no determinista en tiempo polinomial y una posible solución (es decir, un certificado) para un problema en NP se puede verificar para la corrección en tiempo polinomial.

Un ejemplo de una solución no determinista para el problema k-clique sería algo así como:

1) selecciona aleatoriamente k nodos de un gráfico

2) verificar que estos k nodos forman una camarilla.

La estrategia anterior es polinomial en el tamaño del gráfico de entrada y, por lo tanto, el problema k-clique está en NP.

Tenga en cuenta que todos los problemas que se pueden resolver de forma determinista en tiempo polinomial también están en NP.

Demostrar que un problema es NP-hard generalmente implica una reducción de algún otro problema NP-difícil a su problema utilizando un mapeo de tiempo polinomial: http://en.wikipedia.org/wiki/Reduction_(complexity)


15
2017-12-07 01:45