¿Cuáles son las diferencias entre NP, NP-Completo y NP-Duro?
¿cuáles son las diferencias entre NP, NP-Completos y NP-Duro?
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 está ahí fuera, o está ahí fuera y no soy consciente.
10 answers
Asumo que estás buscando definiciones intuitivas, ya que las definiciones técnicas requieren bastante tiempo para entenderlas. En primer lugar, recordemos un concepto preliminar necesario para entender esas definiciones.
- Problema de decisión: Un problema con una respuesta sí o no.
Ahora, definamos esas clases de complejidad.
P
P es una clase de complejidad que representa la conjunto de todos los problemas de decisión que se pueden resolver en tiempo polinómico .
Es decir, dada una instancia del problema, la respuesta sí o no se puede decidir en tiempo polinómico.
Ejemplo
Dado un grafo conectado G, ¿pueden sus vértices ser coloreados usando dos colores para que ninguna arista sea monocromática?
Algoritmo: comience con un vértice arbitrario, coloréelo de rojo y todos sus vecinos de azul y continúe. Detente cuando te quedes sin vértices o se ven obligados a hacer que una arista tenga ambos extremos del mismo color.
NP
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 polinómico.
Esto significa que si alguien nos da una instancia del problema y un certificado (a veces llamado un testigo) de que la respuesta es sí, podemos verificar que es correcta en polinomios tiempo.
Ejemplo
La factorización de enteros está en NP. Este es el problema que dados los enteros n y m, existe un entero f con 1 < f < m, tales 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 da una instancia del problema (por lo que nos dan enteros n y m) y un entero f con 1 < f < m, y afirman que f es un factor de n (el certificado), podemos comprobar la respuesta en tiempo polinómico 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 Y a X en tiempo polinómico.
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 polinómico f para transformar instancias y de Y a instancias x = f(y) de X en tiempo polinómico, 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 (ANDs) de disyunciones de 3 cláusulas (ORs), 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 finita predefinida (x_1, x_2, ... x_n).
Se puede demostrar que cada problema 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 (basada en máquinas de Turing no deterministas). Esto se conoce como teorema de Cook.
Lo que hace que los problemas NP-complete sean importantes es que si se puede encontrar un algoritmo de tiempo polinómico determinista para resolver uno de ellos, cada problema NP es solucionable en tiempo polinómico (un problema para gobernarlos a todos).
NP-duro
Intuitivamente, estos son los problemas que sonal menos tan difíciles como los problemas NP-completos . Tenga en cuenta que los problemas 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, tal que Y es reducible a X en polinomio time .
Pero dado que cualquier problema NP-completo puede ser reducido a cualquier otro problema NP-completo en tiempo polinómico, todos los problemas NP-completos pueden ser reducidos a cualquier problema NP-duro en tiempo polinómico. Entonces, si hay una solución a un problema NP-duro en tiempo polinómico, hay una solución a todos los problemas NP en tiempo polinómico.
Ejemplo
El problema de detención es un problema NP-hard. Este es el problema que dado un programa P y input I, ¿se detendrá? Este es un problema de decisión, pero no está en NP. Está claro que cualquier problema NP-completo puede reducirse a este. Como otro ejemplo, cualquier problema NP-complete es NP-hard.
Mi problema NP-completo favorito es el problema del Buscaminas .
P = NP
Este es el problema más famoso en ciencias de la computación, y una de las cuestiones pendientes más importantes en las ciencias matemáticas. De hecho, la Arcilla Instituto 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 NP tienen o no soluciones de tiempo polinómico deterministas. Se cree en gran medida que no lo hacen. Aquí hay un artículo reciente sobresaliente sobre lo último (y la importancia) del problema P = NP: El Estado del problema P versus NP.
El mejor libro sobre el tema es Computers and Intractability por Garey y Johnson.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-05-24 09:01:30
He estado mirando alrededor y viendo muchas explicaciones largas. Aquí hay un pequeño gráfico que puede ser útil para resumir:
Observe cómo aumenta la dificultad de arriba a abajo: cualquier NP se puede reducir a NP-Completo, y cualquier NP-Completo se puede reducir a NP-Duro, todo en tiempo P (polinomio).
Si puede resolver una clase de problema más difícil en tiempo P, eso significará que encontró cómo resolver todos los problemas más fáciles en tiempo P (por ejemplo, demostrando P = NP, si averiguar cómo resolver cualquier problema NP-Completo en tiempo P).
____________________________________________________________ | 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 Yes o No entradas:
- * Un problema NP que también es P se puede resolver en tiempo P.
- * * Un problema NP-Hard que también es NP-Complete es verificable en tiempo P.
- *** NP-Problemas completos (todos los cuales forman un subconjunto de NP-hard) podría ser. El resto de NP hard no lo es.
También encontré este diagrama bastante útil para ver cómo todos estos tipos corresponden a uno al otro (prestar más atención a la mitad izquierda del diagrama).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-07-23 14:35:04
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 caminar un camino alrededor de todos 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 eficientemente la respuesta, pero si la respuesta es "sí", entonces hay una prueba corta y rápida para verificar. En el primer caso un no trivial factorización 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 sí o no que varían solo en un parámetro. Digamos que el problema COMPOSITE = {"Es n composite": n es un entero} o EULERPATH={"¿El grafo G tiene una ruta 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 but pero si conoces alguna información adicional, es obvio cómo probar que tienes la respuesta correcta. El compuesto es así: la división de prueba es el algoritmo obvio, y es lento: para factorizar un número de 10 dígitos, tienes que probar algo así como 100.000 divisores posibles. Pero si, para ejemplo, alguien le dijo que 61 es un divisor de 3233, división larga simple es una manera eficiente de ver que son correctos.
La clase de complejidad NP es la clase de problemas de decisión donde las respuestas 'sí' tienen un estado corto, rápido para verificar las pruebas. Como COMPUESTO. Un punto importante es que esta definición no dice nada acerca de lo difícil que es el problema. Si tiene una manera correcta y eficiente de resolver un problema de decisión, simplemente escriba los pasos en el la solución es prueba suficiente.
La investigación de algoritmos continúa, y se crean nuevos algoritmos inteligentes todo el tiempo. Un problema que puede no saber cómo resolver de manera eficiente hoy puede llegar a tener una solución eficiente (si no obvia) mañana. De hecho, tomó investigadores hasta 2002 para encontrar una solución eficiente al COMPUESTO! Con todos estos avances, uno realmente tiene que preguntarse: ¿Es esta parte de tener pruebas cortas solo una ilusión? Tal vez 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 NP. Al jugar con los modelos de circuitos para la computación, Stephen Cook encontró un problema de decisión de la variedad NP que era probablemente tan duro o más duro que cada otro problema NP. Una solución eficiente para el problema de satisfacibilidad booleana podría usarse para crear un solución eficiente a cualquier otro problema en NP. Poco después, Richard Karp mostró 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 establecen naturalmente de esta manera: "encontrar los factores de N", "encontrar el camino más corto en el gráfico G que visita cada vértice", " dar un conjunto de asignaciones de variables que hacen verdadera la siguiente expresión booleana". Aunque uno puede hablar informalmente de que algunos de estos problemas están "en NP", técnicamente eso no tiene mucho sentido they no son problemas de decisión. Algunos de estos problemas podrían incluso tener el mismo tipo de poder que un problema NP-completo: una solución eficiente a estos problemas (no decisión) conduciría directamente a una solución eficiente a cualquier problema NP. Un problema como este se llama NP-hard.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-12-07 02:42:44
Además de las otras grandes respuestas, aquí está el esquema típico que la gente usa para mostrar la diferencia entre NP, NP-Complete y NP-Hard:
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-11-24 17:50:15
La forma más fácil de explicar P v.NP y tal sin entrar en tecnicismos es comparar "problemas verbales" con "problemas de opción múltiple".
Cuando usted está tratando de resolver un "problema de palabras" que tiene que encontrar la solución desde cero. Cuando usted está tratando de resolver un "problemas de opción múltiple" que tiene una opción: o resolverlo como lo haría un "problema de palabras", o tratar de conectar cada una de las respuestas dadas a usted, y elegir la respuesta del candidato que se ajuste.
Sucede a menudo que un " problema de opción múltiple "es mucho más fácil que el correspondiente" problema de palabras": sustituir las respuestas del candidato y verificar si encajan puede requerir mucho menos esfuerzo que encontrar la respuesta correcta desde cero.
Ahora, si estuviéramos de acuerdo en el esfuerzo que toma tiempo polinómico "fácil", entonces la clase P consistiría en "problemas verbales fáciles", y la clase NP consistiría en "problemas fáciles de opción múltiple".
La esencia de P v. NP es la pregunta: "¿Hay cualquier problema fácil de opción múltiple que no son fáciles como problemas de palabras"? 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 lo que 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 encontrara una solución a uno de esos problemas "más difíciles de todos" uno sería capaz de encontrar una solución a TODOS los 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, encontrará automáticamente una" solución de problemas de palabras "para todos y cada uno de los"problemas de opción múltiple fácil"!
Finalmente, los problemas NP-complete son aquellos que son simultáneamente NP y NP-hard. Siguiendo nuestra analogía, son simultáneamente "fáciles como opción múltiple problemas " y "los más difíciles de todos como problemas verbales".
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-08-08 20:41:19
P (Tiempo Polinómico) : Como el propio nombre sugiere, estos son los problemas que se pueden resolver en tiempo polinómico.
NP (Tiempo polinómico no determinista) : Estos son los problemas de decisión que se pueden verificar en tiempo polinómico. Eso significa, si afirmo que hay una solución de tiempo polinómico para un problema en particular, me pides que lo demuestre. Luego, le daré una prueba que puede verificar fácilmente en tiempo polinómico. 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 polinómico.
NP-Hard : Estos son al menos tan duros como los problemas más difíciles en NP. Si podemos resolver estos problemas en tiempo polinómico, podemos resolver cualquier problema NP que pueda existir. Tenga en cuenta que estos problemas no son necesariamente problemas NP. Eso significa que podemos / no podemos verificar la solución a estos problemas en tiempo polinómico.
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 NP y las soluciones a estos problemas se pueden verificar en tiempo polinómico.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-06-13 09:18:27
Creo que podemos responder mucho más sucintamente. Respondí a una pregunta relacionada , y copié mi respuesta desde allí
Pero primero, un problema NP-hard es un problema para 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-duro ya probado al "problema-P" en tiempo polinómico.
Para responder el resto de la pregunta, primero debe comprender qué problemas NP-hard también son NP-completo. Si un problema NP-hard pertenece a set NP, entonces es NP-complete. Para pertenecer al conjunto NP, un problema debe ser
I) un problema de decisión,
(ii) the number of solutions to the problem should be finite and each solution should be of polynomial length, and
(iii) dada una solución de longitud polinómica, deberíamos poder decir si la respuesta al problema es sí/noAhora, 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 de traveling salesman donde necesitamos encontrar un horario real es más difícil que la versión de decisión de traveling salesman donde solo necesitamos determinar si existe un horario con longitud
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 11:55:11
Los problemas NP-completos son aquellos problemas que son NP-Duros 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á en NP y que es NP-duro.
Los problemas que están en la clase de complejidad NP se pueden resolver de manera no determinista en tiempo polinómico y una posible solución (es decir, un certificado) para un problema en NP se puede verificar para su corrección en tiempo polinómico.
Un ejemplo de la solución no determinista al problema de la camarilla k sería algo así como:
1) seleccione aleatoriamente k nodos de un gráfico
2) compruebe que estos nodos k 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 deterministamente solucionables en tiempo polinómico también están en NP.
Mostrar que un problema es NP-hard típicamente implica una reducción de algún otro NP-problema difícil para su problema usando una asignación de tiempo polinómica: http://en.wikipedia.org/wiki/Reduction_ (complejidad)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-12-07 01:45:29
Hay respuestas muy agradables para esta pregunta en particular, por lo que no tiene sentido escribir mi propia explicación. Así que voy a tratar de contribuir con un excelente recurso sobre diferentes clases de complejidad computacional.
Para alguien que piensa que la complejidad computacional es solo sobre P y NP, aquí está el recurso más exhaustivo sobre diferentes problemas de complejidad computacional. Aparte de los problemas planteados por la OP, enumeraba 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.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-01-14 01:56:55
Como yo 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-completo es:
- en NP
- np-duro
Int Intro. a Algoritmos (3ed) por Cormen, Leiserson, Rivest, y Stein, pg 1069
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-08-13 13:57:11