¿Qué es “P = NP?” Y por qué es una pregunta tan famosa? [cerrado]

La pregunta de si P = NP es quizás la más famosa en toda la informática. Qué significa eso? ¿Y por qué es tan interesante?

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

P significa tiempo polinomial. NP significa tiempo polinómico no determinista.

Definiciones:

• El tiempo polinómico significa que la complejidad del algoritmo es O (n ^ k), donde n es el tamaño de sus datos (p. Ej., El número de elementos en una lista para ordenar), y k es una constante.

• La complejidad es el tiempo medido en la cantidad de operaciones que tomaría, en función de la cantidad 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 matricial, la operación básica es la multiplicación de dos números.

Ahora la pregunta es, ¿qué significa determinista versus no determinista? Existe un modelo computacional abstracto, una computadora imaginaria llamada máquina de Turing (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 cualquier momento, la TM está en uno de sus estados y está mirando una celda 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 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.

Aquí nos interesan dos tipos de TM: deterministas y no deterministas. Una TM determinista solo tiene una transición de cada estado para cada símbolo que está leyendo en la cinta. Una TM no determinista puede tener varias de esas transiciones, es decir, puede verificar varias posibilidades simultáneamente. Esto es algo así como generar múltiples hilos. La diferencia es que una TM no determinista puede generar tantos "hilos" como desee, mientras que en una computadora real solo se puede ejecutar un número específico de hilos a la vez (igual al número de CPU). En realidad, las computadoras son básicamente TMs deterministas con cintas finitas. Por otro lado, una 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 mediante una TM no determinista puede resolverse mediante una TM determinista. Sin embargo, no está claro cuánto tiempo llevará. El enunciado P = NP significa que si un problema toma tiempo polinomial en una TM no determinista, entonces uno puede construir una 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 NP completo significa un problema NP X, de modo que cualquier problema NP Y puede reducirse a X mediante una reducción polinómica. Eso implica que si a alguien se le ocurre una solución de tiempo polinomial para un problema de NP completo, eso también dará una solución de tiempo polinomial a cualquier problema de NP. Por lo tanto, eso probaría que P = NP. Por el contrario, si alguien demostrara que P! = NP, entonces estaríamos seguros de que no hay forma de resolver un problema de NP en tiempo polinómico 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 requiera tiempo polinómico en la TM no determinista solo se puede hacer en tiempo exponencial en una TM determinista o en una computadora convencional.
Por ejemplo, la única forma de resolver el problema de asignación de verdad es probar 2 ^ n posibilidades.

1. Un problema de sí o no está en P ( tiempo olinomial P ) si la respuesta puede calcularse en tiempo polinomial.
2. Un sí o ningún problema es en NP ( N en determinista P tiempo olynomial) si una respuesta de sí puede ser verificada en tiempo polinómico.

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

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

Hay una gran cantidad de problemas importantes que se sabe que son NP completos (básicamente, si se demuestra que alguno de estos problemas está en P , entonces todos los problemas de NP están en P ). Si P = NP , entonces se demostrará que todos estos problemas tienen una solución eficiente (tiempo polinómico).

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

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 entradas determinadas. Un rompecabezas lógico 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 declaraciones ("George vive en el amarillo casa, cultiva guisantes y es dueño del perro "). Un ejemplo famoso es el problema del vendedor ambulante: dada una lista de ciudades y los horarios para llegar de una ciudad a otra, y un límite de tiempo, una solución potencial sería una lista de ciudades en el orden en que el vendedor las visita, y funcionaría si la suma de los tiempos de viaje fuera inferior al límite de tiempo.

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

(Eficientemente, aquí, tiene un significado matemático preciso. Prácticamente, significa que los grandes problemas no son irrazonablemente difíciles de resolver. Al buscar una posible solución, una forma ineficiente sería enumerar todas las posibles soluciones posibles, o algo parecido a eso , mientras que una forma eficiente requeriría buscar en un conjunto mucho más limitado).

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

Generalmente suponemos que P no es igual a NP, que no hay una forma general de encontrar soluciones. Si resulta 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 el texto cifrado y la clave de manera eficiente y producir el texto original, por lo que si P = NP podríamos encontrar la clave de manera eficiente sin saberlo de antemano. El descifrado de contraseñas se volverí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-complete. Un problema de NP completo es uno que es NP (por supuesto), y tiene esta propiedad interesante: si está en P, cada problema de NP es, y entonces P = NP. Si pudiera encontrar una manera de resolver eficientemente el problema del vendedor ambulante, o rompecabezas lógicos de revistas de rompecabezas, podría resolver cualquier cosa de manera eficiente en NP. Un problema de NP completo es, en cierto modo, el tipo de problema de NP más difícil.

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

Un breve resumen de mi humilde conocimiento:

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

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

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

Es interesante porque nadie tiene ni idea de la solución. Algunos dicen que es cierto, algunos dicen que es falso, pero no hay consenso. Otra cosa interesante es que una solución sería perjudicial para los cifrados de clave pública / privada (como RSA). Podría romperlos tan fácilmente como generar una clave RSA ahora.

Y es un problema bastante inspirador.

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

Primero, algunas definiciones:

• Un problema particular está en P si puede calcular una solución en un tiempo menor que n^kpara algunos k, donde nestá el tamaño de la entrada. Por ejemplo, la ordenación se puede realizar en un valor n log nmenor que n^2, por lo que la ordenación es tiempo polinómico.

• Un problema está en NP si kexiste una solución de tamaño como máximo n^kque puede verificar a tiempo como máximo n^k. Tome 3 colores de gráficos: dado un gráfico, un 3 colores es una lista de pares (vértice, color) que tiene tamaño O(n)y puede verificar a tiempo O(m)(o O(n^2)) si todos los vecinos tienen colores diferentes. Por lo tanto, un gráfico es de 3 colores solo si hay una solución corta y fácilmente verificable.

Una definición equivalente de NP es "problemas solubles por un N máquina de Turing ondeterministic en P tiempo olynomial". 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 puede verificarse en tiempo polinomial; simplemente verifique que la solución dada sea igual a la que puede encontrar.

¿Por qué es P =? NPinteresante la pregunta ? Para responder eso, primero hay que ver qué son los problemas de NP completo. 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 si y 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 computable en tiempo polinómico y tener un tamaño polinómico, en el tamaño de L '; de esa manera, resolver un problema de NP completo en tiempo polinómico nos da una solución de tiempo polinomial a todos los problemas de NP.

Aquí hay un ejemplo: supongamos que sabemos que 3 colores de gráficos es un problema NP-difícil. 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 ...) enumerando todas las configuraciones iguales y estipulación de que ninguna de ellas es el caso.

ANDAl unir todas estas restricciones se obtiene una fórmula booleana que tiene un tamaño polinómico ( O(n+m)). Puede verificar que también se necesita tiempo polinómico para calcular: está haciendo O(1)cosas sencillas 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 coincida con los valores de esas variables. Mediante la construcción de la fórmula, los vecinos no tendrán los mismos colores.

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

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