¿Por qué son los problemas NP llaman de esa manera (y NP-duro y NP-completo)?

Question

En serio .. Estoy teniendo la última prueba para la graduación de este martes, y esa es una de las cosas que nunca pude entender. Soy consciente de que una solución para el problema NP puede verfied en tiempo polinómico. Pero lo que hace el determinismo tiene que ver con eso?
Y si usted me podría explicar dónde NP-completos y NP-duro tiene sus nombres, que sería grande (estoy bastante seguro de que entiendo el significado de ellos, sólo que no ver lo que sus nombres tienen que ver con lo que son).
Lo siento si eso es trivial, simplemente no puedo parecer conseguirlo (-:
Gracias a todos!

Answer 1

P

Clase de todos los problemas que pueden ser resueltos por un determinista máquina de Turing en tiempo polinómico.

NP

Clase de todos los problemas que pueden ser resueltos por un no determinista- máquina de Turing en tiempo polinómico (también pueden ser verificados por un determinista máquina de Turing en tiempo polinómico. )

NP-duro

Una clase de problemas que son "al menos tan duro como los problemas más difíciles en NP". Formalmente, un problema está en NP-duro si y sólo si existe un problema NP-completo que es tiempo polinomial de Turing reducible a ella; (También: si y sólo si se puede resolver en tiempo polinómico por una máquina oráculo con un oráculo para el problema). Es bastante obvio que el nombre proviene de.

NPC

La clase de problemas que son a la vez NP, así como NP-duro. En cuanto a la denominación, incluso Wikipedia no está seguro de por qué es llamado como es.

Answer 2

Empecemos con "no determinista". Una máquina determinista puede estar en un estado a la vez. De hecho, podemos hacerlos. Una máquina no determinista es una construcción teórica que puede estar en más de un estado a la vez. (Hay similitudes con la computación cuántica aquí, pero para nuestros propósitos aquí están engañosa. No tenerlas en cuenta.)

Si queremos resolver un problema con una máquina determinista, partimos hacia arriba, y se pasa a través de una serie de medidas para tratar de encontrar un problema. Si se modela usando una máquina no determinista, se puede ir a través de todos los posibles serie de pasos a la vez.

El conjunto de problemas que vamos a estar preocupados con los problemas de decisión es: dado un planteamiento del problema, o bien no hay una solución o no. Encontrar una solución o informan que no hay ninguno. Por ejemplo, suponga que tiene un conjunto de instrucciones lógicas: A o no-B, B o C o D, no-D o A o B, .... Dado un conjunto arbitrario, se puede encontrar valores de verdad para todas las variables de tal manera que todas las afirmaciones son ciertas?

Ahora, vamos a considerar el P. Supongamos que representamos el tamaño de un problema por n. El tamaño podría ser el número de ciudades en un problema del viajante, el número de estados lógicos en el problema anterior, lo que sea. Dado un cierto n, el problema requerirá una cierta cantidad de recursos para resolver en un sistema dado. Ahora, si duplicamos los recursos o la capacidad computacional, lo que ocurre con el tamaño del problema que podemos resolver? Si el problema es de complejidad polinómica, lo que significa en P, el tamaño sube por una cierta fracción. Podría duplicarse, o subir en un 40%, o el 10%. Por el contrario, si es de complejidad exponencial, el tamaño sube por un determinado número. Generalmente pensamos en los problemas P como problemas solubles e insolubles como exponenciales como los problemas consiguen grandes, aunque eso es una simplificación. Desde un punto de vista informal, la complejidad polinómica es ser capaz de entender las cosas sobre el problema de forma secuencial, mientras exponencial es tener que mirar en todas las combinaciones posibles.

Supongamos que podemos resolver el problema en tiempo polinómico en una máquina determinista. El problema está en P. Supongamos que podemos resolver en tiempo polinómico en una máquina no determinista, que es el mismo que estar en condiciones de verificar una propuesta de solución en tiempo polinómico en una máquina determinista. Entonces el problema está en NP. El truco aquí es que no podemos hacer verdaderas máquinas no deterministas, por lo que el hecho de que un problema está en NP no quiere decir que sea práctico para resolver.

Ahora a NP-completo. Todos los problemas en P están en NP. Para los problemas de A y B en NP, podríamos ser capaces de decir que si A está en P, por lo que se B. Esto se hace mediante la búsqueda de una manera de RESTATE B como un tipo de problema. Un problema NP-completo es uno tal que, si está en P, todos los problemas de NP es en P. Como se puede adivinar, encontrar una manera de repetir todos los problemas posibles como uno en particular no fue fácil, y voy a acaba de decir que el problema con los enunciados lógicos anteriores (el problema satisfacibilidad) fue el primer demostrado NP-completo. Después de que era más fácil, ya que sólo era necesario probar que si el problema estaba en C P, por lo que era satisfacibilidad.

Se cree generalmente que hay problemas que se encuentran en NP pero no P, y una prueba fue publicado recientemente (que puede o no puede llegar a ser válida). En ese caso, los programas de NP-completos son los tipos más duros de problemas en NP.

Hay problemas que no encajan en ese molde. El problema del viajante, como normalmente se plantea, es encontrar la ruta más barata que conecta todas las ciudades. Eso no es un problema de decisión, y no podemos verificar cualquier solución propuesta directamente. Podemos reexpresamos como un problema de decisión: dado un costo de C, no es una ruta que es más barato que C? Este problema es NP-completo, y con un poco de trabajo que puede resolver el TSP original, casi tan fácilmente como el modificado, NP-completo, formulario. Por lo tanto, el TSP es NP-difícil, ya queEs por lo menos tan duro como un problema NP-completo.

Answer 3

NP se llama NP (tiempo polinómico no determinista), porque un problema NP puede ser resuelto en tiempo polinómico por una máquina de Turing no determinista.

Answer 4

El Que comience con NP: en NP, N es para "no determinista" y P es para "tiempo polinómico". Es la clase de problemas que pueden ser resueltos en tiempo polinómico si usted tiene una máquina de Turing no determinista que se ramifican en cada ciclo para explorar las posibilidades en paralelo (el "verificar la solución" definición alternativa se ha popularizado recientemente, pero que no deja claro lo que significa "N"). La máquina no determinista se puede comparar a un ordenador en paralelo con un número infinito de procesadores, y la capacidad de fork() en cada instrucción.

Decir que un problema Q es un medio "NP-duros" que cualquier problema en NP se puede reducir al problema de Q (en tiempo polinómico). Dado que la relación "puede ser reducido a" entre los problemas es una relación de orden, se puede pensar en "NP-duro" en el sentido de "al menos tan duro como todos los problemas NP".

Un problema "NP-completo" no es más que uno de los problemas en NP que es NP-duro. Creo que esa clase de problemas necesitaba un nombre, pero no estoy seguro de cómo explicar la elección de la palabra "completo".

Answer 5

  

Pero lo que hace el determinismo tiene que ver con eso?

Wikipedia :

NP es el conjunto de todos los problemas de decisión para la que los 'yes'-respuestas tienen pruebas verificables de manera eficiente el hecho de que la respuesta es de hecho 'sí'. Más precisamente, estas pruebas tienen que ser verificables en tiempo polinómico por una determinista máquina de Turing

No está seguro acerca de la historia de los nombres sin embargo. EDIT: Tengo conjeturas sin embargo. Lo que sigue es una especulación, pero no creo que es razonable.

NP-duro es ningún problema que es al menos tan duro como los problemas más difíciles en la NP. Por lo tanto, se podría decir que el problema en cuestión tendría dureza NP., Por lo tanto, NP-duro.

Si cualquier problema individual en NP-completo puede resolverse rápidamente, entonces todos los problemas de NP puede también ser resuelto rápidamente. Por lo tanto, el conjunto completo de los problemas NP podría resolverse.

Edit2 de Wikipedia completa (Complejidad) artículo indica:

  

un problema computacional se ha completado para una clase de complejidad si lo es, en un sentido formal, uno de los más expresivos o "" problemas "más duros" en la clase de complejidad