¿Qué son los problemas NP, los problemas NP completos y los problemas NP difíciles?
¿Qué es un problema NP?
Concepto 1:
En informática existe un tipo de problema con algoritmos de tiempo polinomial, llamados problemas tipo P; En cuanto al problema de la Torre del Vaticano, el problema del viaje del vendedor y el problema de satisfacibilidad (expresión proposicional), hay un tipo de problemas que no han sido resueltos mediante algoritmos de tiempo polinómico, que se denominan problemas NP.
Concepto 2:
En la teoría de la complejidad computacional, el tiempo polinómico se refiere al hecho de que el tiempo de cálculo m(n) de un problema no es mayor que el múltiplo polinómico del tamaño del problema. n. Cualquier máquina abstracta tiene una clase de complejidad que incluye problemas que la máquina puede resolver en tiempo polinomial.
En términos de descripción matemática, se puede decir que m(n) = O(n), donde n es un valor constante (dependiendo del problema)
Tome la del vendedor problema de viaje como Por ejemplo, suponga que el vendedor Henry tiene la tarea de vender los productos de la empresa a 6 ciudades y ha especificado un presupuesto de viaje. Tiene una lista de tarifas de vuelo en la mano. Quiere comenzar desde la ciudad A y visitar las 6 ciudades de la imagen y luego regresar a la ciudad A sin exceder el presupuesto. Ayúdelo a encontrar la ruta que debe tomar. Si el presupuesto otorgado es generoso, la tarea es sencilla; si el presupuesto es ajustado, hay que planificar cuidadosamente la ruta. Debe considerar todas las secuencias posibles para minimizar los costos de viaje.
El problema más difícil entre los problemas NP se llama NP-completo y se ha demostrado que incluye: el diseño geométrico óptimo de la red telefónica y el movimiento óptimo del tablero de ajedrez. Según el teorema de Cook, si cualquier problema NP completo se puede resolver en tiempo polinomial, entonces todos los problemas NP se pueden resolver en tiempo polinomial. Sin embargo, todavía no hay respuesta a esta pregunta.
¿Qué es un problema no determinista? Algunos problemas de cálculo son deterministas, como la suma, la resta, la multiplicación y la división. Solo necesitas seguir las fórmulas y seguir los pasos paso a paso para obtener los resultados. Sin embargo, algunos problemas no se pueden calcular directamente paso a paso. Por ejemplo, el problema de encontrar números primos grandes. ¿Existe una fórmula, un conjunto de fórmulas, que pueda ayudarte a calcular paso a paso cuál debería ser el siguiente número primo? No existe tal fórmula. Otro ejemplo es el problema de descomponer un número compuesto grande en factores primos. ¿Existe una fórmula que pueda calcularse directamente sustituyendo el número compuesto en factores primos? Tampoco existe tal fórmula.
La respuesta a este tipo de preguntas no se puede calcular directamente. El resultado sólo se puede obtener mediante "adivinanzas" indirectas. Éste es el problema del no determinismo. Por lo general, existe un algoritmo para estas preguntas que no puede decirle directamente cuál es la respuesta, pero puede decirle si un determinado resultado posible es la respuesta correcta o incorrecta. Este algoritmo que puede decirle si la respuesta a su "suposición" es correcta o no, si se puede calcular en tiempo polinómico (tiempo polinómico: el tiempo de ejecución es como máximo una función polinómica de la cantidad de entrada), se llama polinomio. problema no determinista. Y si todas las respuestas posibles a esta pregunta se pueden verificar correcta o incorrectamente en tiempo polinomial, se denomina problema no determinista completamente polinomial.
La respuesta al problema no determinista de polinomios completos se puede obtener mediante el método exhaustivo. Si compruebas uno por uno, finalmente obtendrás el resultado. Sin embargo, la complejidad de dicho algoritmo es exponencial, por lo que el tiempo de cálculo aumenta exponencialmente con la complejidad del problema y pronto se vuelve incomputable. Se descubrió que todos los problemas no deterministas completamente polinomiales se pueden convertir en un tipo de problemas de operación lógica llamados problemas satisfactorios. Dado que todas las respuestas posibles a este tipo de preguntas se pueden calcular en tiempo polinómico, la gente se ha preguntado si existe un algoritmo determinista para este tipo de preguntas que pueda calcular o buscar directamente la respuesta correcta en tiempo exponencial. ¿Es este el famoso NP=P? conjetura.
Solo hay dos posibilidades para resolver esta conjetura. Una es encontrar dicho algoritmo. Siempre que se encuentre un algoritmo para un problema NP-completo específico, todos esos problemas se pueden resolver fácilmente porque pueden. ser transformado por el mismo problema. Otra posibilidad es que tal algoritmo no exista. Entonces debemos demostrar matemáticamente por qué no existe.
Un logro matemático que causó sensación en el mundo hace algún tiempo fue que unos indios propusieron un nuevo algoritmo que puede demostrar si un determinado número es primo o no en tiempo polinómico. Antes de esto, la gente. Pensé que los números primos La prueba es un problema no polinómico.
Se puede ver que algunos problemas que parecen no polinomiales son en realidad problemas polinomiales, pero la gente aún no conoce sus soluciones polinomiales.
¿Qué es un problema NP y qué es un problema NPC?
Primero explique la diferencia entre la complejidad del problema y la complejidad del algoritmo. A continuación solo se considerará la complejidad del tiempo. . La complejidad del algoritmo se refiere al tiempo de ejecución de un algoritmo específico para resolver el problema, que es la naturaleza del algoritmo; la complejidad del problema se refiere a la complejidad del problema en sí, que es la naturaleza del problema; Por ejemplo, para un problema de clasificación, si solo podemos determinar las posiciones mutuas de los elementos mediante la comparación mutua entre elementos y no hay otra información adicional disponible, la complejidad del problema de clasificación es O (nlgn), pero hay muchas clasificaciones. algoritmos, y existe el riesgo de que el método de la burbuja sea O(n^2), la clasificación rápida sea O(nlgn) en promedio, etc. La complejidad del problema de clasificación se refiere a la complejidad del mejor algoritmo entre todos los algoritmos que resolver el problema. La complejidad del problema no se puede obtener enumerando varios algoritmos posibles. Generalmente, un valor se estima de antemano y luego se prueba teóricamente.
Para estudiar la complejidad del problema debemos abstraer el problema. Para simplificar el problema, solo consideramos un tipo de preguntas simples, problemas de decisión, es decir, hacer una pregunta y solo. necesidad de responder sí o no. Cualquier problema de optimización general se puede transformar en una serie de problemas de decisión. Por ejemplo, encontrar el camino más corto de A a B en el gráfico se puede transformar en: ¿Existe un camino de longitud 1 de A a B? ¿Existe un camino de longitud 2 de A a B? . . . ¿Existe un camino de longitud k de A a B? Si responde que sí cuando le preguntan sobre k, entonces deje de hacer preguntas. Podemos decir que el camino más corto de A a B es k.
Si la complejidad de un problema de decisión es una función polinómica de tamaño n de una instancia del problema, entonces decimos que el problema de decisión que se puede resolver en tiempo polinómico pertenece al tipo de problema P. Los problemas de clase P son el conjunto de todos los problemas con complejidad de tiempo polinomial.
Sin embargo, para algunos problemas es difícil encontrar un algoritmo de tiempo polinomial (quizás no exista en absoluto), como el problema de encontrar un ciclo hamiltoniano en un gráfico no dirigido, pero encontramos que Si nos da una respuesta a este problema, podemos determinar si esta respuesta es correcta en tiempo polinómico. Por ejemplo, para el problema del ciclo hamiltoniano, dado un ciclo arbitrario, podemos determinar fácilmente si es un ciclo hamiltoniano (simplemente observe si todos los vértices están en el ciclo). Este tipo de problema que puede verificar si una solución es correcta en tiempo polinómico se denomina problema NP. Obviamente, todos los problemas de tipo P son problemas NP, pero la pregunta actual es: ¿P es igual a NP? Este problema aún no se ha resuelto. Tenga en cuenta que los problemas NP no son necesariamente difíciles de resolver. Por ejemplo, un problema de clasificación de matrices simple es un problema de tipo P, pero P pertenece a NP, por lo que también es un problema NP. Como acabo de decir, todavía no sabemos si existe P = NP o P <> NP, pero luego la gente descubrió que existen una serie de problemas NP especiales. Las propiedades especiales de estos problemas hacen que mucha gente crea que P. <>NP, pero ahora todavía no se puede demostrar. Este tipo de problema NP especial es un problema NP-completo (problema NPC, C significa completo). El problema NPC tiene una propiedad sorprendente, es decir, si hay un algoritmo de tiempo polinomial para un problema NPC, entonces todos los problemas NP se pueden resolver en tiempo polinomial, es decir, ¡P = NP se cumple! ! Esto se debe a que cada problema NPC se puede transformar en cualquier problema NP en tiempo polinomial. Por ejemplo, el problema del ciclo hamiltoniano mencionado anteriormente es un problema de NPC. La historia de los problemas con los NPC no se remonta a hace mucho tiempo. Cook encontró el primer problema con los NPC en 1971. Desde entonces, la gente ha descubierto muchos problemas con los NPC uno tras otro. Puede que ahora haya más de 3000 problemas con los NPC. Por lo tanto, generalmente pensamos que el problema NPC es un problema difícil porque es poco probable que exista un algoritmo de tiempo polinómico (si existe, entonces todos los problemas NP tienen algoritmos de tiempo polinómico, lo cual es increíble, pero no imposible).
Al igual que el problema del ciclo/ruta hamiltoniano, el problema del vendedor ambulante, el problema del grupo, el problema de cobertura mínima del borde (tenga en cuenta la diferencia con la cobertura de la ruta) y muchos otros problemas son problemas de NPC, por lo que son difíciles. para resolver el problema.