algorithm - np complete problems list

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

Question

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

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

Answer 1

Además de las otras grandes respuestas, aquí está el esquema típico que la gente usa para mostrar la diferencia entre NP, NP-Completo y NP-Duro:

Answer 2

Como lo entiendo, un problema np-hard no es "más difícil" que un problema np-complete . De hecho, por definición, cada problema np-complete es:

1. en NP
2. np-hard

- Introducción. a los algoritmos (3ed) de Cormen, Leiserson, Rivest y Stein, pág. 1069

Answer 3

Creo que podemos responderlo de manera mucho más sucinta. Respondí una pregunta relacionada y copié mi respuesta desde allí.

Pero primero, un problema de NP-duro es un problema para el que no podemos probar que existe una solución de tiempo polinomial. La dureza NP de algunos "problemas-P" generalmente se prueba al convertir un problema NP-ya probado en "problemas-P" en el tiempo polinomial.

Para responder al resto de la pregunta, primero debe comprender qué problemas de NP-hard también son NP-completos. Si un problema de 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) la cantidad de soluciones al problema debe ser finita y cada solución debe ser de longitud polinómica, y
(iii) dada una solución de longitud polinomial, deberíamos poder decir si la respuesta al problema es sí / no

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

Answer 4

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 sendero alrededor de los Siete Puentes de Königsberg sin tomar ningún puente dos veces? Estos son ejemplos de preguntas que comparten un rasgo común. Puede que no sea obvio cómo determinar de manera eficiente la respuesta, pero si la respuesta es ''sí'', entonces hay una prueba breve y rápida para verificar. En el primer caso una factorización no trivial de 51; en el segundo, una ruta para recorrer los puentes (ajustando las restricciones).

Un problema de decisión es un conjunto de preguntas con respuestas de sí o no que varían solo en un parámetro. Diga el problema COMPOSITE = {"Is n composite": n es un entero} o EULERPATH = {"¿El gráfico G tiene una ruta de Euler?": G es un gráfico 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 lento: para factorizar un número de 10 dígitos, debes probar algo así como 100,000 divisores posibles. Pero si, por ejemplo, alguien te dijo que 61 es un divisor de 3233, una división larga simple es una manera eficiente de ver que son correctas.

La clase de complejidad NP es la clase de problemas de decisión en los que las respuestas de "sí" tienen pruebas breves y rápidas para indicar. Al igual que el COMPUESTO. Un punto importante es que esta definición no dice nada acerca de cuán difícil es el problema. Si tiene una forma correcta y eficiente de resolver un problema de decisión, solo la prueba de los pasos en la solución es prueba.

La investigación de los algoritmos continúa y se crean nuevos algoritmos inteligentes todo el tiempo. Un problema que quizás no sepa cómo resolver de manera eficiente hoy puede resultar en tener una solución eficiente (si no obvia) en el futuro. De hecho, llevó a los investigadores hasta 2002 a encontrar una solución eficiente para COMPOSITE. Con todos estos avances, uno realmente tiene que preguntarse: ¿es esto un poco acerca de tener pruebas cortas solo una ilusión? ¿Quizás cada problema de decisión que se presta a pruebas eficientes tiene una solución eficiente? Nadie sabe

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

Por supuesto, NP es solo una clase de problemas de decisión. Muchos problemas no se expresan naturalmente de esta manera: "encuentre los factores de N", "encuentre la ruta más corta en la gráfica G que visita cada vértice", "proporcione un conjunto de asignaciones de variables que hagan que la siguiente expresión booleana sea verdadera". Si bien uno puede hablar informalmente de que algunos de estos 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 potencia que un problema NP-completo: una solución eficiente para estos problemas (sin decisión) llevaría directamente a una solución eficiente para cualquier problema NP. Un problema como este se llama NP-hard .

Answer 5

Hay respuestas realmente agradables para esta pregunta en particular, por lo que no tiene sentido escribir mi propia explicación. Así que intentaré contribuir con un excelente recurso sobre diferentes clases de complejidad computacional.

Para alguien que piensa que la complejidad computacional solo se trata de P y NP, este es el recurso más exhaustivo sobre diferentes problemas de complejidad computacional. Además de los problemas solicitados por OP, enumeró aproximadamente 500 clases diferentes de problemas computacionales con descripciones agradables y también la lista de trabajos de investigación fundamentales que describen la clase.

Answer 6

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 a abajo: cualquier NP puede reducirse a NP-Completo , y cualquier NP-Completo se puede reducir a NP-Duro , todo en tiempo P (polinomio).

Si puede resolver una clase más difícil de problemas en tiempo P, eso significará que encontró cómo resolver todos los problemas más fáciles en tiempo P (por ejemplo, demostrando que P = NP, si encuentra la manera de resolver cualquier problema NP-Completo en P tiempo).

____________________________________________________________ | Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty ___________________________________________________________| | | P | Yes | Yes | | | NP | Yes | Yes or No * | | | NP-Complete | Yes | Unknown | | | NP-Hard | Yes or No ** | Unknown *** | | ____________________________________________________________ V

Notas sobre las entradas Yes o No :

• * Un problema de NP que también es P es solucionable en P tiempo.
• ** Un problema de NP-Hard que también es NP-Complete es verificable en P tiempo.
• *** Los problemas NP-completos (todos los cuales forman un subconjunto de NP-hard) pueden ser. El resto del NP duro no lo es.

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

Answer 7

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

Cuando intenta resolver un "problema de palabra", tiene que encontrar la solución desde cero. Cuando está tratando de resolver un "problema de opción múltiple", tiene una opción: resuélvalo como lo haría con un "problema de palabra", o intente conectar cada una de las respuestas que se le dan, y elija la respuesta candidata que corresponda.

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

Ahora, si estuviéramos de acuerdo con el esfuerzo que hace que el tiempo polinomial sea "fácil", entonces la clase P consistirá en "problemas simples", y la clase NP consistirá 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 tan fácil como un problema verbal"? Es decir, ¿hay problemas para los que 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 opción múltiple" que, en cierto sentido, son los más difíciles de todos: si uno pudiera encontrar 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 problema de palabras" para uno de ellos, encontrará automáticamente una "solución de problema de palabras" para todos y cada uno de los "problemas de opción múltiple".

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

Answer 8

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

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

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

1) Seleccionar al azar 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 de k-clique está en NP.

Tenga en cuenta que todos los problemas resueltos de manera determinista en el tiempo polinomial también están en NP.

Mostrar que un problema es NP-duro generalmente implica una reducción de algún otro problema NP-duro a su problema usando un mapeo de tiempo polinomial: http://en.wikipedia.org/wiki/Reduction_(complexity)

Answer 9

P (Tiempo polinomial): Como su propio nombre sugiere, estos son los problemas que se pueden resolver en el tiempo polinomial.

NP (Tiempo no determinista-polinomial): Estos son los problemas de decisión que se pueden verificar en el tiempo polinomial. Eso significa que si reclamo que hay una solución de tiempo polinomial para un problema particular, me pide que lo pruebe. Luego, te daré una prueba que puedes verificar fácilmente en tiempo polinomial. Este tipo de problemas se llaman problemas de NP. Tenga en cuenta que aquí no estamos hablando de si existe 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 de NP que pueda existir. Tenga en cuenta que estos problemas no son necesariamente problemas de NP. Eso significa que no podemos verificar la solución a estos problemas en el tiempo polinomial.

NP-Completo: 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.

Answer 10

Supongo que está buscando definiciones intuitivas, ya que las definiciones técnicas requieren bastante tiempo para comprenderlas. En primer lugar, recordemos un concepto preliminar necesario para comprender esas definiciones.

• Problema de decisión : Un problema con una respuesta de sí o no .

Ahora, definamos esas 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, dada una instancia del problema, la respuesta sí o no se puede decidir en tiempo polinomial.

Ejemplo

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

Algoritmo: comienza con un vértice arbitrario, coloréalo de rojo y todos sus vecinos de color azul y continúa. Deténgase cuando se quede sin vértices o se vea forzado a hacer que un borde tenga ambos puntos finales del 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 en las que la respuesta es "sí" tienen pruebas que pueden verificarse en tiempo polinomial.

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

Ejemplo

La factorización entera está en NP. Este es el problema de que dados los enteros n y m , ¿hay un entero f con 1 < f < m , de manera que f divide n ( f es un factor pequeño de n )?

Este es un problema de decisión porque las respuestas son sí o no. Si alguien nos entrega una instancia del problema (para que nos entreguen los números enteros n y m ) y un entero f con 1 < f < m , y reclame 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 los cuales es posible reducir cualquier otro problema NP de Y a X en el tiempo polinomial.

Intuitivamente, esto significa que podemos resolver Y rápidamente si sabemos cómo resolver X rápidamente. Precisamente, Y es reducible a X , si hay un algoritmo de tiempo polinomial f para transformar las 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 puede reducirse a 3-SAT . La prueba de esto es técnica y requiere el uso de la definición técnica de NP ( basada en máquinas de Turing no deterministas ). Esto se conoce como el teorema de Cook .

Lo que hace que los problemas NP-completos sean importantes es que si se puede encontrar un algoritmo de tiempo polinomial determinístico para resolver uno de ellos, cada problema NP se puede resolver en tiempo polinomial (un problema para resolverlos todos).

NP-duro

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

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

Pero como cualquier problema de NP-completo se puede reducir a cualquier otro problema de NP-completo en el tiempo polinomial, todos los problemas de NP-completo se pueden reducir a cualquier problema de NP-difícil en el tiempo polinomial. Entonces, si hay una solución a un problema NP-difícil en el tiempo polinomial, hay una solución a todos los problemas NP en el tiempo polinomial.

Ejemplo

El problema de la detención es un problema NP-difícil. Este es el problema que dado 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 de NP-completo se puede reducir a este. Como otro ejemplo, cualquier problema de NP-completo es NP-duro.

Mi problema NP-completo favorito es el problema Buscaminas .

P = NP

Este es el problema más famoso en ciencias de la computación y una de las preguntas pendientes más importantes en las ciencias matemáticas. De hecho, el Instituto Clay está ofreciendo un millón de dólares por una solución al problema (el writeup Stephen Cook 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 soluciones de tiempo polinomiales deterministas. En gran parte se cree que no lo hacen. Aquí hay un artículo reciente destacado 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 intratabilidad por Garey y Johnson.