¿Qué es un NP-completo en informática?

StackOverflow https://stackoverflow.com/questions/210829

Pregunta

¿Qué es un problema NP-completo? ¿Por qué es un tema tan importante en informática?

¿Fue útil?

Solución

NP significa No determinista Polinomio .

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 regular pero que también incluye una función de elección no determinística). Básicamente, una solución debe 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 se puede reducir al problema dado), entonces el problema es NP completo.

Lo más importante 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.

Editar: Como han señalado otros, a menudo hay soluciones de aproximación para problemas 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.

Otros consejos

¿Qué es NP ?

NP es el conjunto de todos los problemas de decisión (preguntas con una respuesta de sí o no ) para el cual las respuestas de 'sí' pueden ser verificadas en tiempo polinomial (O (n k ) donde n es el tamaño del problema, y ?? k es una constante) por una máquina de Turing determinística . El tiempo polinomial a veces se usa 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 mediante 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-Complete si y solo si cualquier otro problema en NP puede transformarse rápidamente (es decir, en tiempo polinomial) en x.

En otras palabras:

  1. x está en NP, y
  2. Todos los problemas en NP son reducible a x

Entonces, lo que hace que NP-Complete sea tan interesante es que si alguno de los problemas de NP-Complete se resolviera rápidamente, entonces todos los problemas de NP se pueden resolver con rapidez.

Consulte también la publicación ¿Qué es " P = NP? & Quot; 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.

NP-Completo significa algo muy específico y debes tener cuidado o la definición será incorrecta. Primero, un problema de NP es un problema de sí / no tal que

  1. Hay pruebas de tiempo polinómico para cada instancia del problema con un " sí " responde que la respuesta es " sí " ;, o (de manera equivalente)
  2. Existe un algoritmo de tiempo polinomial (posiblemente utilizando variables aleatorias) que tiene una probabilidad diferente de cero " sí " si la respuesta a una instancia del problema es " sí " y dirá " no " 100% del tiempo si la respuesta es " no. & Quot; 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

  1. X está en NP, y
  2. 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í " 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 de manera determinista -polinomio-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 hacer lo siguiente: es el P = NP problem ). 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.

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 ejecute en 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, podríamos comprobar si la solución dada es correcta en el tiempo polinomial.

Algunos ejemplos son el problema de satisfacción booleana (o 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 problemas de NP. Definitivamente, tendría un impacto significativo en la informática si se encontrara una solución.

Básicamente, los problemas de este mundo se pueden clasificar como

& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 1) Problema sin solución & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 2) Problema intratable & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 3) NP-Problem & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 4) P-Problema

& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 1) El primero no es una solución al problema. & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 2) El segundo es el tiempo exponencial de necesidad (que es O (2 ^ n) arriba). & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 3) El tercero se llama el NP. & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 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 Tiempo Polinomial, aún no hemos encontrado una solución, pero se puede verificar en 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. El problema de NP Hard 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 educada.

Si está buscando un ejemplo de un problema NP-completo, le sugiero que eche un vistazo a 3-SAT .

La premisa básica es que tienes una expresión en forma normal conjuntiva , que es una forma de diciendo que tiene una serie de expresiones unidas por OR que todos deben ser ciertos: 

(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 en la que cada una de las expresiones OR tenga exactamente 3 booleanos que coincidan: 

(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 especial 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, obtienes $ 1,000,000 , sin mencionar el respeto y la admiración de los informáticos y matemáticos de todo el mundo.

Honestamente, Wikipedia puede 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 puede aplicarse a todos los demás problemas en la categoría NP-Completo.

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 usamos para resolverlos. Así que diremos que todos los problemas que tienen un algoritmo de escalado bien están en P " Y los que tienen un algoritmo de escala pobre están " en NP " ;.

Eso significa que hay muchos problemas simples " en NP " también, porque podemos escribir malos algoritmos para resolver problemas fáciles. Sería bueno saber qué problemas en NP son realmente difíciles, pero no solo queremos decir "es en los que no hemos encontrado un buen algoritmo para". 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, y creo que X es un problema muy 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 donde un buen algoritmo para resolver X podría también ser utilizado, de alguna manera indirecta, para dar una buena Algoritmo para cada otro problema 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.

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 encuentra 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 fuertes, que son excelentes para dar buenas respuestas (¡pero no hay garantías!) Para estos problemas.

Tenga en cuenta que dos problemas muy famosos, el isomorfismo del gráfico y la factorización, no se conocen como P o NP.

He escuchado una explicación, es decir: " NP-Completeness es probablemente una de las ideas más enigmáticas en el estudio de algoritmos. " NP " significa "polinomio no determinista", " y es el nombre de lo que se llama una clase de complejidad a la que pueden pertenecer los problemas. 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? & Quot; Se le proporciona una posible respuesta, 8. Puede verificar esta respuesta en tiempo polinomial usando el algoritmo de, duh, contando las manzanas. El conteo de las manzanas ocurre en O (n) (es decir, notación Big-oh), porque se necesita un paso para contar cada manzana. Para n manzanas, necesitas n pasos. Este problema está en la clase de complejidad NP.

Un problema se clasifica como NP-completo si se puede demostrar que es tanto NP-Hard como verificable en 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

Problema de NP: -

  1. El problema de NP es un problema de este tipo que se puede resolver en un tiempo polinomial no determinista.
  2. El algoritmo no determinista opera en dos etapas.
  3. Etapa de adivinación no determinista & amp; & amp; Etapa de verificación no determinista.

Tipo de problema de Np

  1. NP completo
  2. NP Hard

NP Problema completo: -

1 El problema de decisión A se llama NP completo si tiene dos propiedades siguientes: -

  1. Pertenece a la clase NP.
  2. Cualquier otro problema en NP se puede transformar en P en tiempo polinomial.

Algunos ejemplos: -

  • problema de la mochila
  • problema de suma de subconjuntos
  • Problema de cobertura de vértices

Los problemas NP-completos son un conjunto de problemas para cada uno de los cuales otro problema de NP se puede reducir en tiempo polinomial, y cuya solución Todavía se puede verificar en tiempo polinomial. Es decir, cualquier problema de NP puede ser Transformado en cualquiera de los problemas NP-completos. - Informalmente, un problema de NP-completo es un problema de NP que es al menos tan difícil como " como cualquier otro problema en NP.

un problema de NP es uno donde se puede crear un algoritmo de computadora que verifica una solución en tiempo polinomial.

un problema de NP-Completo es NP, pero también si puede resolverlo en tiempo polinomial (llamado P), todos los problemas de NP son P

Así que hazte crackin '.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top