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

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

NP significa tiempo polinómico no determinista .

Esto significa que el problema puede resolverse en tiempo polinómico 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 poli tiempo. Si ese es el caso, y un problema NP conocido puede resolverse utilizando el problema dado con una entrada modificada (un problema NP puede reducirse al problema dado), entonces el problema es NP completo.

Lo principal que hay que sacar de un problema NP-completo es que no se puede resolver en tiempo polinómico 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 hay soluciones aproximadas para los problemas de NP-Complete. En este caso, la solución aproximada generalmente proporciona un límite de aproximación usando una notación especial que nos dice qué tan cerca está la aproximación.

¿Qué es NP ?

NP es el conjunto de todos los problemas de decisión (preguntas con una respuesta sí o no) para las 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 determinista de Turing . El tiempo polinómico 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 una máquina de Turing determinista puede resolver en tiempo polinómico . Dado que pueden resolverse en tiempo polinómico, también pueden verificarse en tiempo polinómico. 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 cualquier otro problema en NP se puede transformar rápidamente (es decir, en tiempo polinómico) en x.

En otras palabras:

1. x está en NP, y
2. Cada 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.

Ver 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 difíciles de NP son NP (o incluso un problema de decisión), a pesar de tener NPcomo prefijo. Es decir, el NP en NP-hard no significa tiempo polinomial no determinista . Sí, esto es confuso, pero su uso está arraigado y es poco probable que cambie.

NP-Complete significa algo muy específico y hay que tener cuidado o se equivocará la definición. Primero, un problema NP es un problema sí / no tal que

1. Hay una prueba de tiempo polinómico para cada instancia del problema con una respuesta "sí" de que la respuesta es "sí", o (equivalentemente)
2. Existe un algoritmo de tiempo polinómico (posiblemente usando 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 tener 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 tal manera que la respuesta a la instancia Y sea "sí" si y solo si la respuesta X-instancia es "sí".

Si X es NP-completo y existe un algoritmo determinista de tiempo polinómico que puede resolver todas las instancias de X correctamente (0% de falsos positivos, 0% de falsos negativos), entonces cualquier problema en NP puede resolverse en determinista-polinomio- tiempo (por reducción a X).

Hasta ahora, nadie ha ideado un algoritmo de tiempo polinomial tan determinista, pero nadie ha demostrado que no exista (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-Complete (o NP-Hard). Simplemente significa que no puede tener algo que funcione de manera confiable en todas las instancias de un problema de la misma manera que podría ordenar de manera confiable una lista de enteros. Es muy posible que pueda encontrar un algoritmo que funcione muy bien en todas las instancias prácticas de un problema NP-Hard.

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

         1) Problema insoluble 2) Problema intratable 3) Problema NP 4) Problema P

         1) El primero no es la 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 del tiempo polinómico.

NP: refiere el tiempo polinómico aún para encontrar una solución. No estamos seguros de que no haya una solución de tiempo polinómico, pero una vez que proporcione una solución, esta solución puede verificarse en tiempo polinómico.

NP completo: se refiere en tiempo polinómico aún no hemos encontrado una solución, pero se puede verificar en tiempo polinómico. El problema NPC en NP es el problema más difícil, por lo que si podemos demostrar que tenemos una solución P al problema NPC, entonces los problemas NP que se pueden encontrar en la solución P.

NP Hard: refiere que el tiempo polinómico aún no ha encontrado una solución, pero seguro que no se puede verificar en el tiempo polinómico. El problema NP Hard supera la dificultad de NPC.

NP-Complete es una clase de problemas.

La clase Pconsta de aquellos problemas que se pueden resolver en tiempo polinómico . 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 NPconsta de aquellos problemas que son verificables en el tiempo polinómico. Es decir, si se nos da una solución potencial, entonces podríamos verificar si la solución dada es correcta en el tiempo polinómico.

Algunos ejemplos son el problema de la 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-Completesignifica que el problema es al menos tan difícil como cualquier otro 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-complete. Eso significa que una solución a cualquier problema de NP completo es una solución a todos los problemas de NP.

Muchos algoritmos en seguridad dependen del hecho de que no existen soluciones conocidas para problemas NP difíciles. Definitivamente tendría un impacto significativo en la informática si se encontrara una solución.

Es una clase de problemas donde debemos simular todas las posibilidades para asegurarnos de tener la solución óptima.

Hay muchas buenas heurísticas para algunos problemas de NP-Complete, pero en el mejor de los casos son solo una suposición educada.

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 conjuntiva normal , que es una forma de decir que tiene una serie de expresiones unidas por OR que todas deben ser verdaderas:

(a or b) and (b or !c) and (d or !e or f) ...

El problema de 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 a esto podría ser (a = T, b = T, c = F, d = F). Sin embargo, no se ha descubierto ningún algoritmo que resuelva este problema en el caso general en el tiempo polinómico. Lo que esto significa es que la mejor manera de resolver este problema es hacer una conjetura y verificación de fuerza bruta e intentar diferentes combinaciones hasta encontrar 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 puede encontrar un algoritmo de tiempo polinómico para resolver este problema, obtendrá $ 1,000,000 , sin mencionar el respeto y la admiración de los informáticos y matemáticos de todo el mundo.

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 un solo problema NP-Complete en el tiempo P (polinomio), entonces se puede aplicar a todos los demás problemas en la categoría NP-Complete.

Necesitamos separar algoritmos y problemas. Escribimos algoritmos para resolver problemas y 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 estamos tratando de resolver, en lugar de los algoritmos que usamos para resolverlos. Así que diremos que todos los problemas que tienen un algoritmo bien escalado están "en P". Y los que tienen un algoritmo de escalado pobre están "en NP".

Eso significa que muchos problemas simples también están "en NP", porque podemos escribir algoritmos malos para resolver problemas fáciles. Sería bueno saber qué problemas en NP son los realmente difíciles, pero no solo queremos decir "es para los que no hemos encontrado un buen algoritmo". Después de todo, podría encontrar un problema (llámelo X) que creo que necesita un algoritmo súper sorprendente. Le digo al mundo que el mejor algoritmo que se me ocurrió para resolver mal las escalas X, por lo que creo que X es un problema realmente difícil. Pero mañana, tal vez alguien más listo que yo invente un algoritmo que resuelva 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 para los que nadie conoce un buen algoritmo. Entonces, si pudiera demostrar 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 cualquier otro problema en NP. Bueno, ahora la gente podría estar un poco más convencida de que X es un problema realmente complicado. Y en este caso llamamos X NP-Complete.

Las definiciones de los problemas completos de NP anteriores son correctas, pero pensé que podría ser lírico sobre su importancia filosófica ya que nadie ha abordado ese tema todavía.

Casi todos los problemas complejos con los que te encontrarás serán NP completos. Hay algo muy fundamental en esta clase, y que parece ser computacionalmente diferente de los problemas fáciles de resolver. De alguna manera tienen su propio sabor, y no es tan difícil reconocerlos. Esto básicamente significa que cualquier algoritmo moderadamente complejo es imposible de resolver exactamente: programación, optimización, empaquetado, cobertura, etc.

Pero no todo se pierde si un problema que encontrará es NP Completo. Hay un campo vasto y muy técnico en el que las personas estudian algoritmos de aproximación, lo que le dará garantías de estar cerca de la solución de un problema completo de NP. 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 sobresalen en dar excelentes respuestas (¡pero no garantías!) Para estos problemas.

Tenga en cuenta que dos problemas muy famosos (isomorfismo gráfico y 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 "tiempo polinomial no determinista" y es el nombre de lo que se llama una clase de complejidad para qué problemas pueden pertenecer. Lo importante de la clase de complejidad NP es que los problemas dentro de esa clase se pueden verificarpor un algoritmo de tiempo polinómico. 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 polinómico usando el algoritmo de, duh, contar las manzanas. El conteo de las manzanas ocurre en el tiempo O (n) (eso es 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 NP-Hard y verificable en tiempo polinómico. Sin profundizar demasiado en la discusión de NP-Hard, basta con decir que hay ciertos problemas para los que no se han encontrado soluciones de tiempo polinomiales. Es decir, se necesita algo así como n! (n factorial) pasos para resolverlos. Sin embargo, si le dan una solución a un problema de NP-Complete, puede verificarlo en tiempo polinómico.

Un ejemplo clásico de un problema NP-Complete es El problema del vendedor ambulante ".

El autor: ApoxyButt De: http://www.everything2.com/title/NP-complete

Problema NP: -

1. El problema NP es un problema que puede resolverse en un tiempo polinómico no determinista.
2. El algoritmo no determinista opera en dos etapas.
3. Etapa de adivinanzas no determinista && 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 las siguientes dos propiedades: -

1. Pertenece a la clase NP.
2. Cualquier otro problema en NP puede transformarse en P en tiempo polinómico.

Algunos ex: -

• Problema de mochila
• problema de suma de subconjunto
• Problema de cobertura de vértices

Los problemas NP completos son un conjunto de problemas para cada uno de los cuales cualquier otro problema NP puede reducirse en tiempo polinómico, y cuya solución aún puede verificarse en tiempo polinómico. Es decir, cualquier problema de NP puede transformarse en cualquiera de los problemas de NP completo. - Informalmente, un problema de NP completo es un problema de NP que es al menos tan "difícil" como cualquier otro problema en NP.

Hasta donde yo entiendo

P es el conjunto de problemas que podrían resolverse en tiempo polinómico con una TM determinista.

NP es el conjunto de problemas que requiere un TM no determinista para ser resuelto en tiempo polinómico. Esto significa verificar paralelamente todas las variables posibles, cada instancia toma tiempo polinomial. Si el problema tiene solución, al menos uno de esos estados paralelos debe tener la solución al problema. Esto también significa que si adivinó las variables de la solución, entonces lo único que necesita es verificar la validez de la solución en tiempo polinómico.

NP-Hard es el conjunto donde los problemas son al menos tan difíciles como NP. Cualquier problema en NP podría transformarse en un problema NP-Hard en tiempo polinómico. Estos problemas no pueden resolverse en tiempo polinómico si P no es igual a NP. Es entonces cuando el problema más difícil en NP es el tiempo polinómico solucionable, entonces solo los problemas NP-Hard son solucionables en tiempo polinómico.

NP-Complete es el conjunto de intersección de NP y NP-Hard. Cualquier problema de NP podría transformarse en un problema de NP-Completo en tiempo polinómico. Eso significa que si cualquiera de los NP-Complete podría tener una solución eficiente, cualquier problema de NP podría resolverse con la misma eficiencia.

Por favor, avíseme si cometí algún error.

Un problema NP es aquel en el que se puede crear un algoritmo informático que verifica una solución en tiempo polinómico.

un problema NP-Complete es NP, pero también si puede resolverlo en tiempo polinómico (llamado P), entonces todos los problemas NP son P.

Así que ponte manos a la obra.