computer science - ¿Por qué los problemas de NP se llaman de esa manera(y NP-hard y NP-complete)?
computer-science complexity-theory (5)
¿Pero qué tiene que ver el determinismo con eso?
De Wikipedia :
NP es el conjunto de todos los problemas de decisión para los cuales las respuestas de ''sí'' tienen pruebas verificables eficientemente del hecho de que la respuesta es de hecho ''sí''. Más precisamente, estas pruebas tienen que ser verificables en tiempo polinomial por una máquina de Turing determinista
Aunque no estoy seguro de la historia de los nombres. EDITAR: tengo conjeturas sin embargo. Lo que sigue es especulación, pero no creo que sea irrazonable.
NP-Hard es cualquier problema que es al menos tan difícil como los problemas más difíciles en NP. Por lo tanto, podría decirse que el problema en cuestión tendría una dureza NP, por lo tanto NP-Hard.
Si cualquier problema en NP-completo puede resolverse rápidamente, entonces todos los problemas en NP también pueden resolverse rápidamente. Por lo tanto, el conjunto completo de problemas de NP podría ser resuelto.
EDIT2 : artículo completo de Wikipedia (Complejidad) indica:
un problema computacional está completo para una clase de complejidad si es, en un sentido formal, uno de los problemas "más difíciles" o "más expresivos" en la clase de complejidad
Realmente ... Tengo la última prueba para graduarme este martes, y esa es una de las cosas que nunca pude entender. Me doy cuenta de que una solución para un problema de NP puede verificarse en tiempo polinomial. ¿Pero qué tiene que ver el determinismo con eso?
Y si pudiera explicarme de dónde obtuvieron sus nombres NP-completo y NP-hard, sería genial (estoy bastante seguro de que entiendo su significado, simplemente no veo qué tienen que ver sus nombres con lo que ellos dicen). son).
Lo siento si eso es trivial, parece que no puedo entenderlo (-:
¡Gracias a todos!
PAG
Clase de todos los problemas que pueden resolverse mediante una máquina de Turing determinista en tiempo polinomial.
notario público
Clase de todos los problemas que pueden resolverse con una máquina de Turing no determinista en tiempo polinomial (también pueden ser verificados por una máquina de Turing determinista en tiempo polinomial).
NP-Duro
Una clase de problemas que son "al menos tan difíciles como los problemas más difíciles en NP". Formalmente, un problema se encuentra en NP-Hard si hay un problema NP-completo que es polinomial en tiempo de Turing-reducible a él; (También: iff puede resolverse en tiempo polinomial mediante una máquina oracle con un oracle para el problema). Es bastante obvio de donde viene el nombre.
NPC
La clase de problemas que son tanto NP como NP-Hard. Con respecto a la denominación, incluso wikipedia no está seguro de por qué se llama así.
Empecemos por "no deterministas". Una máquina determinista puede estar en un estado a la vez. En realidad 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í son engañosos. No los tenga en cuenta).
Si queremos resolver un problema con una máquina determinista, lo iniciamos y se realiza una serie de pasos para tratar de encontrar un problema. Si modelamos utilizando una máquina no determinista, puede pasar por todas las series de pasos posibles al mismo tiempo.
El conjunto de problemas que nos preocuparán son los problemas de decisión: dada una declaración de problema, ya sea que haya una solución o no. Encuentre una solución o informe que no hay ninguna. Por ejemplo, suponga que tiene un conjunto de sentencias lógicas: A o no-B, B o C o D, no-D o A o B, ... Dado un conjunto arbitrario, ¿puede encontrar valores de verdad para todas las variables? tal que todas las afirmaciones son ciertas?
Ahora, consideremos la P. Supongamos que representamos el tamaño de un problema con n. El tamaño podría ser el número de ciudades en un problema de vendedor ambulante, el número de declaraciones lógicas 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, ¿qué sucede con el tamaño del problema que podemos resolver? Si el problema es de complejidad polinomial, lo que significa que en P, el tamaño aumenta en una cierta fracción. Puede duplicarse, o subir un 40%, o un 10%. En contraste, si es de complejidad exponencial, el tamaño aumenta en un número determinado. En general, pensamos que los problemas de P son solubles y los problemas exponenciales no se resuelven a medida que los problemas aumentan, aunque eso es una simplificación. Desde un punto de vista informal, la complejidad polinomial es poder resolver cosas sobre el problema de manera secuencial, mientras que exponencial es tener que mirar todas las combinaciones posibles.
Supongamos que podemos resolver el problema en tiempo polinomial en una máquina determinista. El problema está en P. Supongamos que podemos resolverlo en tiempo polinomial en una máquina no determinista, que es lo mismo que poder verificar una solución propuesta en tiempo polinomial 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 significa que sea práctico de resolver.
Ahora en NP-completa. Todos los problemas en P están en NP. Para los problemas A y B en NP, podríamos decir que si A está en P, también lo es B. Esto se hace encontrando una manera de repetir B como un tipo de problema. Un problema de NP-completo es tal que, si está en P, todos los problemas en NP están en P Como puede suponer, encontrar una manera de repetir cada problema posible como uno en particular no fue fácil, y simplemente diga que el problema con las declaraciones lógicas anteriores (el problema de Satisfacción) fue el primer NP-completo probado. Después de eso fue más fácil, ya que solo era necesario demostrar que si el problema C estaba en P, también era Satisfiabilidad.
En general, se cree que hay problemas en NP pero no en P, y recientemente se publicó una prueba (que puede o no resultar válida). En ese caso, los programas NP-completos son los problemas más difíciles en NP.
Hay problemas que no encajan en este molde. El problema del vendedor ambulante, como se plantea normalmente, es encontrar la ruta más barata que conecta todas las ciudades. Eso no es un problema de decisión, y no podemos verificar ninguna solución propuesta directamente. Podemos reformularlo como un problema de decisión: dado un costo C, ¿hay una ruta más barata que C? Este problema es NP-completo, y con un poco de trabajo podemos resolver el TSP original tan fácilmente como el formulario modificado, NP-completo. Por lo tanto, el TSP es NP-duro, ya que es al menos tan difícil como un problema NP-completo.
NP se denomina NP (tiempo polinomial no determinista) porque un problema de NP se puede resolver en tiempo polinomial mediante una máquina de cálculo no determinista.
Comencemos con NP: en NP, N es para "no determinista" y P es para "tiempo polinomial". Es la clase de problemas que se pueden resolver en tiempo polinomial si tiene una máquina de Turing no determinista que puede ramificarse en cada ciclo para explorar posibilidades en paralelo (la definición alternativa "verificar la solución" se ha hecho popular recientemente, pero no queda claro. lo que significa "N"). La máquina no determinista se puede comparar con una computadora paralela con un número infinito de procesadores y la capacidad de fork() en cada instrucción.
Decir que un problema Q es "NP-duro" significa que cualquier problema en NP puede reducirse al problema Q (en tiempo polinomial). Dado que la relación "puede reducirse a" entre problemas es una relación de orden, puede pensar que "NP-hard" significa "al menos tan difícil como todos los problemas de NP".
Un problema "NP-completo" es simplemente uno de los problemas en NP que es NP-duro. Supongo que esa clase de problemas necesitaba un nombre, pero no estoy seguro de cómo explicar la elección de la palabra "completa".