¿Cuáles son las diferencias entre los NP, NP-Completos, y NP-Duro?

Question

¿Cuáles son las diferencias entre NP, NP-Completos y NP-Duro?

Soy consciente de que muchos de los recursos de toda la web.Me gustaría leer tus explicaciones, y la razón es que podría ser diferente de lo que hay, o hay algo que no estoy al tanto de.

Answer 1

Supongo que usted está buscando intuitiva definiciones, ya que las definiciones técnicas requieren bastante tiempo para entender.Primero de todo, vamos a recordar un preliminar necesario concepto para entender esas definiciones.

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

---

Ahora, vamos a definir los la complejidad de las clases.

P

P es la complejidad de la clase que representa el conjunto de todos los problemas de decisión que pueden ser resueltos en tiempo polinomial.

Es decir, dada una instancia del problema, la respuesta sí o no, puede ser decidido en el polinomio de tiempo.

Ejemplo

Dado un grafo conexo G, sus vértices pueden ser de color el uso de dos colores de manera que ningún borde es monocromática?

Algoritmo:empezar con un vértice arbitrario, de color rojo y todos sus vecinos azul y continuar.Detener cuando se ejecuta fuera de los vértices o se ve obligado a hacer un borde tienen ambos de sus extremos, de ser del mismo color.

---

NP

NP es una complejidad de la clase que representa el conjunto de todos los problemas de decisión para los cuales las instancias donde la respuesta es "sí" tiene pruebas de que puede ser verificado en el polinomio de tiempo.

Esto significa que si alguien nos da una instancia del problema y un certificado (a veces llamado un testigo) a la respuesta está sí, podemos comprobar que es correcto en el polinomio de tiempo.

Ejemplo

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

Esta es una decisión problema porque las respuestas son sí o no.Si alguien nos da una instancia del problema (por lo que de la mano 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 polinomio tiempo al realizar la división n / f.

---

NP-Completos

NP-Completo es de una complejidad de la clase que representa el conjunto de todos los problemas X en NP para los que es posible reducir cualquier otro problema NP Y a X en el polinomio de tiempo.

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

Ejemplo

3-SAT.Este es el problema en el que se da una conjunción (And) de 3-cláusula de disyunciones (Sro), las 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 a partir de un número finito de una lista predefinida (x_1, x_2, ... x_n).

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

Lo que hace NP-completos, problemas importante es que si un determinista polinomio tiempo algoritmo se puede encontrar para resolver uno de ellos, cada NP problema es solucionable en el polinomio de tiempo (un problema para gobernarlos a todos).

---

NP-duro

Intuitivamente, estos son los problemas que se al menos tan duro como el NP-completos, problemas.Tenga en cuenta que NP-hard problemas no tiene que ser en NP, y ellos no tienen que ser los problemas de decisión de.

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

Pero dado que cualquier NP-completos problema se puede reducir a cualquier otro tipo NP-completo problema en el polinomio de tiempo, todos los NP-completos, los problemas pueden ser reducidos a cualquier NP-duro problema en el polinomio de tiempo.Entonces, si hay una solución a un NP-duro problema en el polinomio de tiempo, no es una solución a todos los problemas NP en el polinomio de tiempo.

Ejemplo

El detener problema es NP-duro problema.Este es el problema de que, dado un programa P y de entrada I, va a detener?Esta es una decisión problema, pero no está en NP.Está claro que cualquier NP-completos problema se puede reducir a este.Como otro ejemplo, cualquier NP-completos problema es NP-duro.

Mi favorito NP-completo es el problema Buscaminas problema.

---

P = NP

Este es el más famoso problema en ciencias de la computación, y una de las más importantes cuestiones pendientes en las ciencias matemáticas.De hecho, la Instituto Clay se ofrece un millón de dólares para la solución del problema (Stephen Cook valoración crítica en la Arcilla sitio web es bastante buena).

Es claro que P es un subconjunto de NP.La pregunta abierta es si o no NP problemas deterministas polinomio tiempo de soluciones.Es en gran parte cree que no.Aquí hay un excelente artículo reciente en la última (y la importancia) de la P = NP problema: El Estado de la P versus NP problema.

El mejor libro sobre el tema es Los equipos y la Severidad por Garey y Johnson.

Answer 2

He estado buscando por allí y ver muchas explicaciones largas. Aquí es una pequeña tabla que puede ser útil para resumir:

Observe cómo dificultad aumenta de arriba a abajo: cualquier NP puede ser reducido a NP-completo , y cualquier NP-completo se puede reducir a NP-duro , todo en P (polinomio) tiempo.

Si se puede resolver una clase más difícil del problema a tiempo P, eso significa que has encontrado la forma de resolver todos los problemas más fáciles en el tiempo P (por ejemplo, demostrando P = NP, si usted encontrar la manera de resolver cualquier NP problema completo en el 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 las entradas Yes o No:

• * Un problema NP que es también P es resoluble en el tiempo P.
• ** Un problema NP-duro, que también es NP-completo es verificable en el tiempo P.
• *** problemas NP-completos (todos los cuales forman un subconjunto de NP-duro) que podría ser. El resto de NP duro no lo es.

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

Answer 3

Esta es una respuesta muy informal a la pregunta formulada.

Puede 3233 escribirse como el producto de otros dos números más grande que 1? ¿Hay alguna manera de caminar un camino alrededor de toda la siete puentes de Königsberg sin tomar cualquier puente dos veces? Estos son ejemplos de preguntas que comparten un rasgo común. Puede que no sea evidente cómo determinar de manera eficiente la respuesta, pero si la respuesta es 'sí', entonces hay un corto y rápido para comprobar la prueba. En el primer caso una factorización no trivial de 51; en el segundo, una ruta para caminar los puentes (encajando las restricciones).

problema de decisión es una colección de preguntas con respuestas de sí o no, que varían sólo en un parámetro. Decir que el problema COMPUESTO = { "Está compuesta n": n es un entero o} = {EULERPATH "¿El G gráfico de tener un camino de Euler?": G es un gráfico finito}.

Ahora, algunos problemas de decisión se prestan a la eficiente, si no algoritmos obvias. 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 conoces alguna pieza adicional de información, es obvio cómo hacer para demostrar que tienes la respuesta correcta. COMPUESTO es la siguiente: Sección de Primera Instancia es el algoritmo obvio, y es lenta: para factorizar un número de 10 dígitos, que tiene que intentar algo así como 100.000 divisores posibles. Pero si, por ejemplo, alguien le ha dicho que el 61 es un divisor de 3233, la división larga simple es una forma eficiente para ver si es correcta.

La clase de complejidad NP es la clase de los problemas de decisión, donde las respuestas afirmativas tienen corta a estado y rápidos para comprobar pruebas. Como compuesto. Un punto importante es que esta definición no dice nada acerca de lo difícil que es el problema. Si usted tiene una manera correcta y eficiente para resolver un problema de decisión, simplemente anotando los pasos de la solución es prueba suficiente.

Algoritmos la investigación continúa, y nuevos algoritmos inteligentes se crean todo el tiempo. Un problema que quizá no sabe cómo resolver eficientemente hoy puede llegar a tener un eficiente (si no es obvio) solución mañana. De hecho, se llevó a los investigadores hasta que 2002 para encontrar una solución eficiente a COMPUESTO! Con todos estos avances, uno realmente tiene que preguntarse: ¿Es este bit de tener pruebas cortas sólo una ilusión? Tal vez todos problema de decisión que se presta a las pruebas eficiente tiene una solución eficiente? Nadie sabe .

Tal vez la mayor contribución a este campo vino con el descubrimiento de una clase peculiar de los problemas NP. Por jugar con modelos de circuitos de computación, Stephen Cook encontró un problema de decisión de la variedad NP que era demostrablemente tan duro o más duro que todos otro problema NP. Una solución eficaz para la problema satisfacibilidad boolean podría ser utilizado para crear un eficiente solución a cualquier otra problema en NP. Poco después, Richard Karp demostró que una serie de otros problemas de decisión podría servir para el mismo propósito. Estos problemas, en un sentido los problemas "más duros" en NP, fueron conocidos como NP-completos problemas.

Por supuesto, NP es solamente una clase de problemas de decisión. Muchos problemas no se presentan de forma natural en esta forma: "encontrar los factores de N", "encontrar el camino más corto en el grafo G que visita cada vértice", "dan una serie de asignaciones de variables que se hace la siguiente expresión booleana verdadera". Aunque uno puede informalmente talk sobre algunos de estos problemas son "NP", técnicamente que no tiene mucho sentido - no son los problemas de decisión. Algunos de estos problemas podrían incluso tener el mismo tipo de poder como un problema NP-completo: una solución eficaz a estos (no-decisión) problemas conduciría directamente a una solución eficiente a cualquier problema NP. Un problema de este tipo se llama NP-duro .

Answer 4

Además de las otras grandes respuestas, aquí está el esquema típico personas utilizan para mostrar la diferencia entre NP, NP-completo, y NP-duro:

Answer 5

P (Polynomial Time): Como su propio nombre indica, estos son los problemas que pueden ser resueltos en tiempo polinómico

.

NP (Tiempo no determinista-polinomio): Estos son los problemas de decisión que pueden ser verificados en tiempo polinómico. Eso significa que, si reclamo que existe una solución de tiempo polinómico para un problema particular, en mi opinión para probarlo. A continuación, voy a darle una prueba de que se puede comprobar fácilmente en tiempo polinómico. Este tipo de problemas se llama problemas NP. Tenga en cuenta que, aquí no estamos hablando acerca de si hay una solución para el tiempo polinómico o no este problema. Pero estamos hablando de la verificación de la solución a un problema dado en tiempo polinómico.

NP-duro: Estos son por lo menos tan duro como los problemas más difíciles en la NP. Si podemos resolver estos problemas en tiempo polinómico, podemos resolver cualquier problema NP que posiblemente puede existir. Tenga en cuenta que estos problemas no son necesariamente los problemas NP. Eso significa, que podría / no-verificar la solución a estos problemas en tiempo polinómico.

NP-Completo: Estos son los problemas que son a la vez NP y NP-duro. 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.

Answer 6

La forma más fácil de explicar P v. NP y tal, sin entrar en detalles técnicos es comparar "problemas" con la palabra "múltiples problemas de elección".

Cuando usted está tratando de resolver un "problema de palabras" usted tiene que encontrar la solución a partir de cero. Cuando usted está tratando de resolver un "múltiples problemas de elección" tiene una elección: o resolverlo como si fuera un "problema de palabras", o pruebe a conectar en cada una de las respuestas dadas a usted, y escoger la respuesta candidato que se ajuste.

A menudo sucede que un "problema de elección múltiple" es mucho más fácil que el correspondiente "problema de palabras":. Sustituyendo las respuestas candidatos y comprobar si se ajustan puede requerir un esfuerzo significativamente menor que encontrar la respuesta correcta a partir de cero

Ahora, si estamos de acuerdo en el esfuerzo que requiere tiempo polinomio "fácil", entonces la clase P consistiría en "sencillos problemas de palabras", y la clase NP consistiría en "fáciles múltiples problemas de elección".

.

La esencia de P v NP es la pregunta: "¿Hay múltiples problemas de elección fácil que no son fáciles como problemas de palabras"? Es decir, hay problemas para los que es fácil de 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 a nuestra intuición. Resulta que hay "múltiples problemas de elección" que, en cierto sentido, son más difícil de todos: si uno quiere encontrar una solución a uno de los "más difíciles de todos ellos" problemas de uno sería capaz de encontrar una solución a todos problemas NP! Cuando Cook descubrió esto hace 40 años, fue una completa sorpresa. Estos "más duros de ellos todos los" problemas se conocen como NP-duro. Si encuentra una "solución problema palabra" a uno de ellos se encontraría automáticamente una "solución de la palabra problema" a todos y cada uno "problema de elección múltiple fácil"!

Finalmente, los problemas NP-completos son aquellos que son al mismo tiempo NP y NP-duro. Siguiendo la analogía, que son al mismo tiempo "fácil como múltiples problemas de elección" y "el más difícil de todos ellos como problemas de palabras".

Answer 7

Creo que podemos responder a ella mucho más sucinta. Le contesté una pregunta relacionada , y la copia de mi respuesta desde allí

Pero en primer lugar, un problema NP-duro es un problema para el que no podemos probar que existe una solución en tiempo polinomial. NP-dureza de algunos "problema-P" generalmente se demuestra por la conversión de una ya probada problema NP-duro para el "problema-P" en tiempo polinómico.

  

Para responder a la pregunta resto, primero tiene que entender que los problemas NP-duro también son NP-completo. Si un problema NP-duro pertenece al conjunto NP, entonces es NP-completo. Para pertenecerá a la serie NP, un problema tiene que 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 polinomio, y
  (Iii) dado una solución longitud polinómica, debemos ser capaces de decir si la respuesta al problema es si / no

     

Ahora, es fácil darse cuenta de que podría haber muchos problemas NP-duro que no pertenecen al conjunto NP y son más difíciles de resolver. A modo de ejemplo intuitiva, la optimización-versión del viajante de comercio, donde tenemos que encontrar un calendario real es más dura que la toma de versión del viajante de comercio, donde sólo tenemos que determinar si un horario con una longitud <= k existe o no.

Answer 8

problemas NP-completos son aquellos problemas que son a la vez NP-duro como en la clase de complejidad NP. Por lo tanto, para demostrar que cualquier problema dado es NP-completo, es necesario demostrar que el problema es tanto en NP y que es NP-duro.

Los problemas que se encuentran en la clase de complejidad NP pueden ser resueltos no determinista en tiempo polinómico y una solución posible (es decir, un certificado) para un problema en NP pueden ser verificados por la corrección en tiempo polinómico.

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

1) seleccionar aleatoriamente k nodos de un gráfico

2) verificar que estos nodos k forman un clique.

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 pueden resolverse de manera determinista en tiempo polinómico también están en NP.

Mostrando que es un problema NP-duro normalmente implica una reducción de algún otro problema NP-duro para su problema usando un mapeo tiempo polinómico: http://en.wikipedia.org/wiki/Reduction_ (complejidad)

Answer 9

Hay muy buenas respuestas para esta pregunta en particular, así que no hay punto de escribir mi propia explicación. Así que voy a tratar de contribuir con un excelente recurso sobre las diferentes clases de complejidad computacional.

Para alguien que cree que la complejidad computacional es sólo alrededor de P y NP, aquí es la recurso más exhaustiva sobre los diferentes problemas de complejidad computacional . Aparte de los problemas planteadas por OP, que aparece alrededor de 500 diferentes clases de problemas de cálculo con buenas descripciones y también la lista de trabajos de investigación fundamentales que describen la clase.

Answer 10

Como yo lo entiendo, una np-duro el problema no es "más difícil" que un np-completos problema.De hecho, por definición, todos los np-completos problema es:

1. en NP
2. np-duro

-- Intro.a los Algoritmos (3ed) por Cormen, Leiserson, Rivest, y Stein, pg 1069

Answer 11

Para algunos Defintion interesante: