algorithm - hard - ¿Qué es un NP-completo en informática?
np complete problems (15)
¿Qué es un problema NP-completo? ¿Por qué es un tema tan importante en la informática?
¿Qué es NP ?
NP es el conjunto de todos los problemas de decisión (preguntas con una respuesta de sí o no) para las cuales las respuestas de "sí" se pueden verificar en tiempo polinomial (O (n k ) donde n es el tamaño del problema, y k es un constante) por una máquina determinista de turing . El tiempo polinomial se usa a veces como la definición de rápido o rápido .
¿Qué es P ?
P es el conjunto de todos los problemas de decisión que pueden resolverse en tiempo polinomial por una máquina de Turing determinista . Como pueden resolverse en tiempo polinomial, también pueden verificarse en tiempo polinomial. Por lo tanto, P es un subconjunto de NP.
¿Qué es NP-Complete ?
Un problema x que está en NP también está en NP-Completo si y solo si todos los demás problemas en NP pueden transformarse rápidamente (es decir, en tiempo polinomial) en x.
En otras palabras:
- x está en NP, y
- Todo problema en NP es reducible a x
Entonces, lo que hace que NP-Complete sea tan interesante es que si alguno de los problemas NP-Complete se resolviera rápidamente, entonces todos los problemas NP se pueden resolver rápidamente.
Consulte también la publicación ¿Qué es "P = NP?", Y ¿por qué es una pregunta tan famosa?
¿Qué es NP-Hard ?
NP-Hard son problemas que son al menos tan difíciles como los problemas más difíciles en NP. Tenga en cuenta que los problemas NP-Complete también son NP-hard. Sin embargo, no todos los problemas NP-duros son NP (o incluso un problema de decisión), a pesar de tener NP como prefijo. Ese es el NP en NP-duro no significa tiempo polinomial no determinista . Sí, esto es confuso, pero su uso está arraigado y es poco probable que cambie.
Problema de NP: -
- Los problemas de NP son problemas que pueden resolverse en tiempo polinomial no determinista.
- El algoritmo no determinista opera en dos etapas.
- Etapa de adivinación no determinista y & Etapa de verificación no determinística.
Tipo de problema de Np
- NP completo
- NP Duro
NP Completo problema: -
1 El problema de decisión A se llama NP completo si tiene las siguientes dos propiedades:
- Pertenece a la clase NP.
- Cualquier otro problema en NP se puede transformar en P en tiempo polinomial.
Algunos Ex: -
- Problema de la mochila
- problema de suma de subconjuntos
- Vértice cubriendo problema
Básicamente los problemas de este mundo se pueden categorizar como
1) Problema no solucionable 2) Problema intratable 3) Problema NP 4) Problema P
1) El primero no es una solución al problema. 2) El segundo es el tiempo exponencial de necesidad (que es O (2 ^ n) arriba). 3) El tercero se llama el NP. 4) El cuarto es problema fácil.
P: se refiere a una solución del problema del Tiempo Polinomial.
NP: se refiere al tiempo polinomial aún para encontrar una solución. No estamos seguros de que no haya una solución de Tiempo Polinomial, pero una vez que proporcione una solución, esta solución se puede verificar en Tiempo Polinomial.
NP Completo: se refiere en el Tiempo Polinomial que todavía tenemos que encontrar una solución, pero se puede verificar en el Tiempo Polinomial. El problema NPC en NP es el problema más difícil, así que si podemos probar que tenemos una solución P para el problema NPC, entonces los problemas NP que se pueden encontrar en la solución P.
NP Hard: se refiere al tiempo polinomial aún no se ha encontrado una solución, pero seguro que no se puede verificar en el tiempo polinomial. NP El problema difícil supera la dificultad NPC.
Es una clase de problemas en los que debemos simular todas las posibilidades para asegurarnos de que tenemos la solución óptima.
Hay un montón de buenas heurísticas para algunos problemas de NP-Completa, pero son, en el mejor de los casos, una suposición bien fundamentada.
Hay una muy buena conferencia de arsdigita sobre matemáticas discretas que explica qué es un problema de NP-completo.
Los primeros 50 minutos son principalmente sobre álgebra booleana. Así que salte al comienzo del minuto 53 si solo está interesado en los conceptos de P, NP, NP-completidad, el problema de la booleana de satisfacción y la reducción.
He escuchado una explicación, es decir: "NP-Integridad es probablemente una de las ideas más enigmáticas en el estudio de algoritmos." NP "significa" tiempo polinomial no determinista ", y es el nombre de lo que se llama una clase de complejidad para a qué problemas pueden pertenecer. Lo importante de la clase de complejidad NP es que los problemas dentro de esa clase pueden verificarse mediante un algoritmo de tiempo polinomial. Como ejemplo, considere el problema de contar cosas. Supongamos que hay un montón de manzanas en una mesa. El problema es "¿Cuántas manzanas hay?". Se le proporciona una posible respuesta, 8. Puede verificar esta respuesta en tiempo polinomial usando el algoritmo de, por ejemplo, contando las manzanas. El conteo de las manzanas ocurre en O (n) (eso es notación Big-oh), porque se necesita un paso para contar cada manzana. Para n manzanas, necesita n pasos. Este problema está en la clase de complejidad NP.
Un problema se clasifica como NP-completo si se puede demostrar que es NP-Duro y verificable en el tiempo polinomial. Sin profundizar demasiado en la discusión de NP-Hard, basta con decir que hay ciertos problemas para los cuales no se han encontrado soluciones de tiempo polinomial. Es decir, se necesita algo como n! Pasos (n factoriales) para resolverlos. Sin embargo, si se le da una solución a un problema NP-Completo, puede verificarlo en tiempo polinomial.
Un ejemplo clásico de un problema NP-completo es El problema del vendedor ambulante ".
El autor: ApoxyButt De: http://www.everything2.com/title/NP-complete
Honestamente, Wikipedia podría ser el mejor lugar para buscar una respuesta a esto.
Si NP = P, entonces podemos resolver problemas muy difíciles mucho más rápido de lo que pensábamos antes. Si resolvemos solo un problema NP-Completo en tiempo P (polinomio), entonces se puede aplicar a todos los demás problemas en la categoría NP-Completo.
Las definiciones de los problemas completos de NP anteriores son correctas, pero pensé que podría aclarar su importancia filosófica ya que nadie ha abordado ese tema todavía.
Casi todos los problemas complejos con los que se encontrará serán NP completos. Hay algo muy fundamental en esta clase, y que parece ser computacionalmente diferente de los problemas de fácil solución. Ellos tienen su propio sabor, y no es tan difícil reconocerlos. Básicamente, esto significa que es imposible resolver exactamente cualquier algoritmo moderadamente complejo: programación, optimización, empaquetado, cobertura, etc.
Pero no todo se pierde si un problema que encontrará es NP Completo. Existe un vasto y muy técnico campo donde las personas estudian algoritmos de aproximación, que le brindarán garantías para estar cerca de la solución de un problema de NP completo. Algunas de estas son garantías increíblemente sólidas; por ejemplo, para 3sat, puede obtener una garantía de 7/8 a través de un algoritmo realmente obvio. Aún mejor, en realidad, hay algunas heurísticas muy sólidas, que son excelentes para dar excelentes respuestas (¡pero sin garantías!) Para estos problemas.
Tenga en cuenta que dos problemas muy famosos, el isomorfismo gráfico y el factoraje, no se conocen como P o NP.
Los problemas de NP-completa son un conjunto de problemas a los que se puede reducir cualquier otro problema de NP en el tiempo polinomial, y cuya solución aún puede verificarse en el tiempo polinomial. Es decir, cualquier problema de NP se puede transformar en cualquiera de los problemas de NP-completa. - Informalmente, un problema NP-completo es un problema NP que es al menos tan "difícil" como cualquier otro problema en NP.
NP-Complete es una clase de problemas.
La clase P consiste en aquellos problemas que se pueden resolver en tiempo polinomial . Por ejemplo, podrían resolverse en O (n k ) para alguna constante k, donde n es el tamaño de la entrada. En pocas palabras, puede escribir un programa que se ejecutará en un tiempo razonable .
La clase NP consiste en aquellos problemas que son verificables en tiempo polinomial. Es decir, si se nos da una solución potencial, entonces podríamos verificar si la solución dada es correcta en el tiempo polinomial.
Algunos ejemplos son el problema de la satisfacción booleana ( SAT ) o el problema del ciclo hamiltoniano. Hay muchos problemas que se sabe que están en la clase NP.
NP-Complete significa que el problema es al menos tan difícil como cualquier problema en NP.
Es importante para la informática porque se ha demostrado que cualquier problema en NP puede transformarse en otro problema en NP-completo. Eso significa que una solución para cualquier problema NP-completo es una solución para todos los problemas NP.
Muchos algoritmos en seguridad dependen del hecho de que no existen soluciones conocidas para los problemas difíciles de NP. Definitivamente tendría un impacto significativo en la informática si se encontrara una solución.
NP-Completo significa algo muy específico y debes tener cuidado o obtendrás una definición incorrecta. Primero, un problema de NP es un problema de sí / no tal que
- Existe una prueba de tiempo polinómico para cada instancia del problema con una respuesta "sí" que indica que la respuesta es "sí" o (de manera equivalente)
- Existe un algoritmo de tiempo polinomial (posiblemente utilizando variables aleatorias) que tiene una probabilidad distinta de cero de responder "sí" si la respuesta a una instancia del problema es "sí" y dirá "no" el 100% del tiempo si la respuesta es no." En otras palabras, el algoritmo debe tener una tasa de falsos negativos inferior al 100% y no falsos positivos.
Un problema X es NP-Completo si
- X está en NP, y
- Para cualquier problema Y en NP, hay una "reducción" de Y a X: un algoritmo de tiempo polinomial que transforma cualquier instancia de Y en una instancia de X de modo que la respuesta a la instancia de Y sea "sí" si y solo si la respuesta X-instancia es "sí".
Si X es NP-completo y existe un algoritmo determinista, polinomial-tiempo que puede resolver todos los casos de X correctamente (0% de falsos positivos, 0% de falsos negativos), entonces cualquier problema en NP se puede resolver en determinista-polinomial- Tiempo (por reducción a X).
Hasta ahora, nadie ha ideado un algoritmo de tiempo polinomial tan determinista, pero nadie ha probado que no exista uno (hay un millón de dólares para cualquiera que pueda hacerlo: el problema es P = NP ). Eso no significa que no pueda resolver una instancia particular de un problema NP-Completo (o NP-Duro). Simplemente significa que no puede tener algo que funcione de manera confiable en todas las instancias de un problema de la misma manera en que podría ordenar de manera confiable una lista de enteros. Es muy posible que pueda encontrar un algoritmo que funcione muy bien en todos los casos prácticos de un problema NP-Hard.
Necesitamos separar algoritmos y problemas. Escribimos algoritmos para resolver problemas, y se escalan de cierta manera. Aunque esto es una simplificación, etiquetemos un algoritmo con una ''P'' si la escala es lo suficientemente buena, y ''NP'' si no lo es.
Es útil saber cosas sobre los problemas que intentamos resolver, en lugar de los algoritmos que utilizamos para resolverlos. Así que diremos que todos los problemas que tienen un algoritmo de escalado son "en P". Y los que tienen un algoritmo de baja escala están "en NP".
Eso significa que muchos problemas simples también están "en NP", porque podemos escribir algoritmos erróneos para resolver problemas fáciles. Sería bueno saber qué problemas en NP son realmente difíciles, pero no solo queremos decir "para eso no hemos encontrado un buen algoritmo". Después de todo, podría encontrar un problema (llámelo X) que creo que necesita un algoritmo asombroso. Le digo al mundo que el mejor algoritmo que podría encontrar para resolver X escalas mal, por lo que creo que X es un problema realmente difícil. Pero mañana, tal vez alguien más listo que yo inventa un algoritmo que resuelve X y está en P. Así que esta no es una muy buena definición de problemas difíciles.
De todos modos, hay muchos problemas en NP que nadie conoce un buen algoritmo. Entonces, si pudiera probar que X es un cierto tipo de problema: uno en el que un buen algoritmo para resolver X también podría usarse, de alguna manera indirecta, para dar un buen algoritmo para todos los demás problemas en NP. Bueno, ahora la gente podría estar un poco más convencida de que X es un problema realmente difícil. Y en este caso llamamos X NP-Complete.
Si está buscando un ejemplo de un problema de NP-completo, le sugiero que eche un vistazo a 3-SAT .
La premisa básica es que tiene una expresión en forma normal conjuntiva , que es una forma de decir que tiene una serie de expresiones unidas por OR que todo debe ser verdadero:
(a or b) and (b or !c) and (d or !e or f) ...
El problema 3-SAT es encontrar una solución que satisfaga la expresión donde cada una de las expresiones OR tiene exactamente 3 booleanos para coincidir:
(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...
Una solución para esto podría ser (a = T, b = T, c = F, d = F). Sin embargo, no se ha descubierto ningún algoritmo que solucione este problema en el caso general en tiempo polinomial. Lo que esto significa es que la mejor manera de resolver este problema es hacer esencialmente una suposición y verificación de fuerza bruta y probar diferentes combinaciones hasta que encuentre una que funcione.
Lo que es especial acerca del problema 3-SAT es que CUALQUIER problema NP-completo puede reducirse a un problema 3-SAT. Esto significa que si puedes encontrar un algoritmo de tiempo polinomial para resolver este problema, obtendrás $1,000,000 , sin mencionar el respeto y la admiración de los informáticos y matemáticos de todo el mundo.
un problema de NP es uno donde se puede crear un algoritmo de computadora que verifica una solución en tiempo polinomial.
un problema NP-Completo es NP, pero también si puede resolverlo en tiempo polinomial (llamado P), entonces todos los problemas NP son P.
Así que hazte crackin ''.
NP significa tiempo polinomial no determinista .
Esto significa que el problema se puede resolver en tiempo polinomial usando una máquina de Turing no determinista (como una máquina de Turing normal pero que también incluye una función de "elección" no determinista). Básicamente, una solución tiene que ser comprobable en tiempo de poli. Si ese es el caso, y un problema conocido de NP se puede resolver utilizando el problema dado con la entrada modificada (un problema de NP puede reducirse al problema dado), entonces el problema es NP completo.
Lo principal para eliminar un problema de NP-completo es que no se puede resolver en tiempo polinomial de ninguna manera conocida. NP-Hard / NP-Complete es una forma de mostrar que ciertas clases de problemas no se pueden resolver en tiempo real.
Edición: Como otros han señalado, a menudo hay soluciones de aproximación para problemas de NP-Complete. En este caso, la solución de aproximación generalmente proporciona un límite de aproximación utilizando una notación especial que nos dice qué tan cerca está la aproximación.