computer science - science - ¿Qué es “P=NP?” Y por qué es una pregunta tan famosa?

p np np complete (6)

La pregunta de si P = NP es quizás la más famosa de todas las ciencias de la computación. Qué significa eso? ¿Y por qué es tan interesante?

Ah, y para obtener crédito adicional, envíe una prueba de la verdad o falsedad de la declaración. :)

Un problema de sí o no está en P (tiempo mediomial) si la respuesta se puede calcular en tiempo polinomial.
Un sí o ningún problema es en NP (N en determinista P tiempo olynomial) si una respuesta de sí se puede verificar en tiempo polinómico.

Intuitivamente, podemos ver que si un problema está en P , entonces está en NP . Dada una posible respuesta para un problema en P , podemos verificar la respuesta simplemente recalculando la respuesta.

Menos obvio, y mucho más difícil de responder, es si todos los problemas en NP están en P. ¿El hecho de que podamos verificar una respuesta en tiempo polinomial significa que podemos calcular esa respuesta en tiempo polinomial?

Hay un gran número de problemas importantes que se sabe que son NP -Complete (básicamente, si cualquier de estos problemas son probados para estar en P, entonces todos los problemas NP son probados para estar en P). Si P = NP , se comprobará que todos estos problemas tienen una solución eficiente (tiempo polinomial).

La mayoría de los científicos creen que P ! = NP . Sin embargo, aún no se ha establecido ninguna prueba para P = NP o P ! = NP . Si alguien proporciona una prueba para cualquiera de las conjeturas, ganará US $ 1 millón .

No hay mucho que pueda agregar al qué y al por qué de la parte P =? NP de la pregunta, pero con respecto a la prueba. Una prueba no solo valdría un crédito adicional, sino que resolvería uno de los problemas del milenio . Recientemente se realizó una encuesta interesante y los resultados publicados (PDF) definitivamente valen la pena leer con respecto al tema de una prueba.

P significa tiempo polinomial. NP significa tiempo polinomial no determinista.

Definiciones:

El tiempo polinomial significa que la complejidad del algoritmo es O (n ^ k), donde n es el tamaño de sus datos (por ejemplo, número de elementos en una lista a clasificar), y k es una constante.
La complejidad es el tiempo medido en el número de operaciones que tomaría, en función del número de elementos de datos.
La operación es lo que tiene sentido como una operación básica para una tarea en particular. Para ordenar la operación básica es una comparación. Para la multiplicación de matrices, la operación básica es la multiplicación de dos números.

Ahora la pregunta es, ¿qué significa determinista vs. no determinista? Hay un modelo computacional abstracto, una computadora imaginaria llamada Turing machine (TM). Esta máquina tiene un número finito de estados y una cinta infinita, que tiene celdas discretas en las que se puede escribir y leer un conjunto finito de símbolos. En un momento dado, la TM se encuentra en uno de sus estados y está mirando una celda en particular en la cinta. Dependiendo de lo que lea de esa celda, puede escribir un nuevo símbolo en esa celda, mover la cinta una celda hacia adelante o hacia atrás y pasar a un estado diferente. Esto se llama una transición de estado. Sorprendentemente, al construir cuidadosamente estados y transiciones, puede diseñar una TM, que es equivalente a cualquier programa de computadora que se pueda escribir. Es por esto que se usa como un modelo teórico para probar cosas sobre lo que las computadoras pueden y no pueden hacer.

Hay dos tipos de TM que nos preocupan aquí: deterministas y no deterministas. Un TM determinista solo tiene una transición de cada estado para cada símbolo que está leyendo de la cinta. Un TM no determinista puede tener varias de estas transiciones, es decir, es capaz de verificar varias posibilidades simultáneamente. Esto es algo así como generar múltiples hilos. La diferencia es que un TM no determinista puede generar tantos "subprocesos" como quiera, mientras que en una computadora real solo se puede ejecutar un número específico de subprocesos a la vez (igual al número de CPU). En realidad, las computadoras son básicamente TMs deterministas con cintas finitas. Por otro lado, un TM no determinista no puede realizarse físicamente, excepto tal vez con una computadora cuántica.

Se ha demostrado que cualquier problema que pueda resolverse con un TM no determinista se puede resolver con un TM determinista. Sin embargo, no está claro cuánto tiempo tomará. La declaración P = NP significa que si un problema toma tiempo polinomial en un TM no determinista, entonces se puede construir un TM determinista que resolvería el mismo problema también en tiempo polinomial. Hasta ahora nadie ha podido demostrar que se puede hacer, pero nadie ha podido demostrar que tampoco se puede hacer.

El problema de NP-completo significa un problema de NP X, de modo que cualquier problema de NP Y puede reducirse a X mediante una reducción polinómica. Eso implica que si alguien alguna vez se le ocurre una solución de tiempo polinomial a un problema de NP completa, eso también dará una solución de tiempo polinomial a cualquier problema de NP. Por lo tanto eso probaría que P = NP. A la inversa, si alguien probara que P! = NP, entonces estaríamos seguros de que no hay manera de resolver un problema de NP en tiempo polinomial en una computadora convencional.

Un ejemplo de un problema NP-completo es el problema de encontrar una asignación de verdad que haría que una expresión booleana que contiene n variables sea verdadera.
Por el momento, en la práctica, cualquier problema que lleve tiempo polinomial en el TM no determinista solo se puede hacer en tiempo exponencial en un TM determinista o en una computadora convencional.
Por ejemplo, la única manera de resolver el problema de la asignación de la verdad es probando 2 ^ n posibilidades.

Para dar la respuesta más simple que se me ocurre:

Supongamos que tenemos un problema que requiere un cierto número de entradas y tiene varias soluciones potenciales, que pueden o no resolver el problema para determinadas entradas. Un rompecabezas de la lógica en una revista de rompecabezas sería un buen ejemplo: las entradas son las condiciones ( "George no vive en la casa azul o verde"), y la solución potencial es una lista de instrucciones ( "George vive en el amarillo Casa, cultiva guisantes, y posee el perro "). Un ejemplo famoso es el problema del viajante: dada una lista de las ciudades, y los tiempos para llegar desde cualquier ciudad de cualquier otro, y un límite de tiempo, una posible solución sería una lista de ciudades en el orden que el vendedor de los visita, y funcionaría si la suma de los tiempos de viaje fuera menor que el límite de tiempo.

Tal problema está en NP si podemos verificar de manera eficiente una solución potencial para ver si funciona. Por ejemplo, dada una lista de ciudades para el vendedor para visitar en orden, podemos sumar los tiempos para cada viaje entre las ciudades, y fácilmente ver si está por debajo del límite de tiempo. Un problema está en P si podemos encontrar una solución eficaz si existe una.

(De manera eficiente, aquí, tiene un significado matemático preciso. En la práctica, esto significa que los grandes problemas no son excesivamente difíciles de resolver. Durante la búsqueda de una posible solución, una forma ineficiente sería enumerar todas las posibles soluciones potenciales, o algo parecido a eso , mientras que una forma eficiente requeriría buscar un conjunto mucho más limitado.)

Por lo tanto, el problema P = NP se puede expresar de esta manera: Si se puede verificar una solución para un problema del tipo descrito anteriormente de manera eficiente, se puede encontrar una solución (o demostrar que no hay ninguno) de manera eficiente? La respuesta obvia es "¿Por qué deberías poder hacerlo?", Y eso es prácticamente lo que ocurre hoy en día. Nadie ha podido demostrarlo de una manera u otra, y eso molesta a muchos matemáticos y científicos de la computación. Es por eso que cualquiera que pueda probar que la solución está ganando un millón de dólares de la Fundación Claypool.

En general, asumimos que P no es igual a NP, que no hay una forma general de encontrar soluciones. Si resultara que P = NP, muchas cosas cambiarían. Por ejemplo, la criptografía se volvería imposible, y con ella cualquier tipo de privacidad o verificabilidad en Internet. Después de todo, podemos tomar de manera eficiente el texto cifrado y la clave y producir el texto original, por lo que si P = NP que hemos podido encontrar la clave de manera eficiente sin saberlo de antemano. El craqueo de contraseñas sería trivial Por otro lado, hay clases enteras de problemas de planificación y problemas de asignación de recursos que podríamos resolver de manera efectiva.

Es posible que haya escuchado la descripción NP-completa. Un problema NP-completo es uno que es NP (por supuesto), y tiene esta propiedad interesante: si está en P, todos los problemas NP es, y por lo tanto P = NP. Si pudiera encontrar una manera de resolver de manera eficiente el problema del vendedor ambulante o los rompecabezas de lógica de las revistas de rompecabezas, podría resolver cualquier cosa de manera eficiente en NP. Un problema de NP-completo es, en cierto modo, el tipo más difícil de problema de NP.

Por lo tanto, si puede encontrar una técnica de solución general eficiente para cualquier problema de NP-completo o probar que no existe, la fama y la fortuna son suyas.

Primero, algunas definiciones:

Un problema particular está en P si puede calcular una solución en el tiempo menor que n^k para algunos k , donde n es el tamaño de la entrada. Por ejemplo, la clasificación se puede hacer en n log n que es menor que n^2 , por lo que la clasificación es tiempo polinomial.
Un problema está en NP si existe una k tal que existe una solución de tamaño como máximo n^k que puede verificar a tiempo como máximo n^k . Toma 3 colores de gráficos: dado un gráfico, un color 3 es una lista de pares (vértice, color) que tiene el tamaño O(n) y puedes verificar en el tiempo O(m) (o O(n^2) ) Si todos los vecinos tienen colores diferentes. Por lo tanto, un gráfico es tridimensional solo si hay una solución corta y fácilmente verificable.

Una definición equivalente de NP es "problemas solucionables por una máquina de Turing Ndeterministist en el tiempo Ponyomial". Si bien eso le dice de dónde viene el nombre, no le da la misma sensación intuitiva de cómo son los problemas de NP.

Tenga en cuenta que P es un subconjunto de NP: si puede encontrar una solución en tiempo polinomial, hay una solución que se puede verificar en tiempo polinomial; simplemente verifique que la solución dada sea igual a la que puede encontrar.

¿Por qué la pregunta P =? NP P =? NP interesante? Para responder a eso, uno primero necesita ver cuáles son los problemas NP-completos. En pocas palabras,

Un problema L es NP-completo si (1) L está en P, y (2) un algoritmo que resuelve L puede usarse para resolver cualquier problema L ''en NP; es decir, dada una instancia de L '', puede crear una instancia de L que tenga una solución solo si la instancia de L'' tiene una solución. Hablando formalmente, cada problema L ''en NP es reducible a L.

Tenga en cuenta que la instancia de L debe ser polinomial en tiempo computable y tener un tamaño polinomial, en el tamaño de L ''; de esa manera, resolver un problema de NP-completa en el tiempo polinomial nos da una solución de tiempo polinomial para todos los problemas de NP.

Aquí hay un ejemplo: supongamos que sabemos que los 3 colores para gráficos son un problema difícil de NP. Queremos demostrar que decidir la satisfacción de las fórmulas booleanas también es un problema NP-difícil.

Para cada vértice v, tenga dos variables booleanas v_h y v_l, y el requisito (v_h o v_l): cada par solo puede tener los valores {01, 10, 11}, que podemos considerar como color 1, 2 y 3.

Para cada borde (u, v), tenga el requisito de que (u_h, u_l)! = (V_h, v_l). Es decir,

not ((u_h and not u_l) and (v_h and not v_l) or ...) enumerar todas las configuraciones iguales y la estipulación de que ninguna de ellas es el caso.

AND al juntar todas estas restricciones se obtiene una fórmula booleana que tiene un tamaño polinomial ( O(n+m) ). También puede verificar que se necesita tiempo polinomial para calcular: está haciendo cosas O(1) directas por vértice y por borde.

Si puede resolver la fórmula booleana que he creado, también puede resolver la coloración del gráfico: para cada par de variables v_h y v_l, deje que el color de v sea el que coincida con los valores de esas variables. Por la construcción de la fórmula, los vecinos no tendrán colores iguales.

Por lo tanto, si la coloración en 3 de los gráficos es NP-completa, también lo es la satisfacibilidad de la fórmula booleana.

Sabemos que 3-coloración de gráficos es NP-completa; sin embargo, históricamente hemos llegado a saber eso al mostrar primero la integridad de NP de la capacidad de satisfacción del circuito booleano, y luego reducirlo a 3 colores (en lugar de al revés).

Un breve resumen de mi humilde conocimiento:

Hay algunos problemas de cálculo fáciles (como encontrar la ruta más corta entre dos puntos en un gráfico), que se puede calcular bastante rápido (O (n ^ k), donde n es el tamaño de la entrada y k es una constante (en caso de que de gráficos, es el número de vértices o aristas)).

Otros problemas, como encontrar una ruta que cruce cada vértice en un gráfico o obtener la clave privada RSA de la clave pública son más difíciles (O (e ^ n)).

Pero CS habla dice que el problema es que no podemos "convertir" una máquina de Turing no determinista a una determinista; sin embargo, podemos transformar autómatas finos no deterministas (como el analizador de expresiones regulares) en factores deterministas (bueno, puede, pero el tiempo de ejecución de la máquina tomará mucho tiempo). Es decir, tenemos que intentar todos los caminos posibles (por lo general, los profesores inteligentes de CS pueden excluir algunos).

Es de descanso, porque nadie tiene ni idea de la solución. Algunos dicen que es verdad, otros dicen que es falso, pero no hay consenso. Otra cosa interesante es que una solución podría ser perjudicial para las inscripciones de claves públicas / privadas (como RSA). Podría romperlas tan fácilmente como generar una clave RSA ahora.

Y es un problema bastante inspirador.