¿Qué es un NP-completo en informática? [cerrado]
¿Qué es un problema NP-completo? ¿Por qué es un tema tan importante en informática?
¿ Qué es el NP ?
NP es el conjunto de todos los problemas de decisión (preguntas con respuesta sí o no) para los cuales las respuestas 'sí' pueden verificarse en tiempo polinómico (O(n k ) donde n es el tamaño del problema y k es un constante) por una máquina de Turing determinista . El tiempo polinómico se utiliza a veces como 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 polinómico mediante una máquina determinista de Turing . Como se pueden resolver en tiempo polinomial, también se pueden verificar en tiempo polinomial. Por tanto P es un subconjunto de NP.
¿Qué es NP-Completo ?
Un problema x que está en NP también está en NP-Completo si y sólo 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 cualquiera de los problemas de NP-Complete se resolviera rápidamente, entonces todos los problemas de 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-Duro ?
NP-Difíciles son problemas que son al menos tan difíciles como los problemas más difíciles de NP. Tenga en cuenta que los problemas NP-Completos también son NP-difíciles. Sin embargo, no todos los problemas NP-difíciles son NP (o incluso un problema de decisión), a pesar de tener NPcomo prefijo. Que NP en NP-hard no signifique tiempo polinómico no determinista . Sí, esto es confuso, pero su uso está arraigado y es poco probable que cambie.
NP significa tiempo polinómico no determinista .
Esto significa que el problema se puede resolver en tiempo polinómico utilizando 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 debe poder probarse en tiempo poli. Si ese es el caso, y un problema NP conocido se puede resolver usando el problema dado con entrada modificada (un problema NP se puede reducir al problema dado), entonces el problema es NP completo.
Lo principal que se puede sacar de un problema 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 un tiempo realista.
Editar: Como otros han señalado, a menudo existen soluciones aproximadas para los problemas NP-Complete. En este caso, la solución aproximada generalmente proporciona un límite de aproximación usando una notación especial que nos indica qué tan cerca está la aproximación.
Básicamente, los problemas de este mundo se pueden clasificar como
1) Problema sin solución 2) Problema intratable 3) Problema NP 4) Problema P
1) La primera no es una solución al problema. 2) El segundo es el tiempo exponencial necesario (es decir, O (2 ^ n) arriba). 3) El tercero se llama NP. 4) El cuarto es un problema fácil.
P: se refiere a una solución del problema de Tiempo Polinomial.
NP: se refiere al Tiempo Polinómico aún por encontrar una solución. No estamos seguros de que no exista 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 Tiempo Polinomial aún tenemos que encontrar una solución, pero se puede verificar en Tiempo Polinomial. El problema NPC en NP es el problema más difícil, por lo que si podemos demostrar que tenemos una solución P para el problema de NPC, entonces los problemas NP 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 tiempo polinomial. El problema NP Hard supera la dificultad NPC.
Jul 19 '2013 04:07