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

Question

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

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

Answer 1

P representa el tiempo polinómico.NP significa tiempo polinómico no determinista.

Definiciones:

• Tiempo polinomial significa que la complejidad del algoritmo es O(n^k), donde n es el tamaño de sus datos (e.gramo.número de elementos en una lista a ordenar), y k es una constante.

• Complejidad Es el tiempo medido en el número de operaciones que tomaría, en función del número de elementos de datos.

• Operación es cualquier cosa que tenga sentido como operación básica para una tarea 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.media 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 dado, la MT se encuentra en uno de sus estados y está mirando una celda particular de la cinta.Dependiendo de lo que lea en 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.A esto se le llama transición de estado.Sorprendentemente, al construir cuidadosamente estados y transiciones, se puede diseñar una MT, que es equivalente a cualquier programa de computadora que pueda escribirse.Por eso se utiliza como modelo teórico para demostrar cosas sobre lo que las computadoras pueden y no pueden hacer.

Hay dos tipos de MT que nos conciernen aquí:determinista y no determinista.Una TM determinista solo tiene una transición de cada estado para cada símbolo que lee en la cinta.Una MT no determinista puede tener varias transiciones de este tipo, i.mi.es capaz de comprobar varias posibilidades simultáneamente.Esto es algo así como generar múltiples hilos.La diferencia es que una MT no determinista puede generar tantos "hilos" como quiera, mientras que en una computadora real sólo se puede ejecutar una cantidad específica de subprocesos a la vez (igual a la cantidad de CPU).En realidad, las computadoras son básicamente memorias de traducción deterministas con cintas finitas.Por otro lado, una MT no determinista no se puede realizar físicamente, excepto tal vez con una computadora cuántica.

Se ha demostrado que cualquier problema que pueda resolverse mediante una MT no determinista puede resolverse mediante una MT determinista.Sin embargo, no está claro cuánto tiempo llevará.La afirmación P=NP significa que si un problema requiere tiempo polinomial en una TM no determinista, entonces se 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 tampoco nadie ha podido demostrar que no se puede hacer.

Un problema NP-completo significa un problema NP X, tal que cualquier problema NP Y puede reducirse a X mediante una reducción polinomial.Eso implica que si a alguien se le ocurre alguna vez una solución en tiempo polinomial para un problema NP completo, eso también dará una solución en tiempo polinomial a cualquier problema NP.Por tanto, eso demostrarí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 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 haga verdadera una expresión booleana que contenga n variables.
Por el momento, en la práctica, cualquier problema que requiera tiempo polinomial en una TM no determinista sólo puede resolverse 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.

Answer 2

1. Un problema de sí o no está en PAG (PAGtiempo polinomial) si la respuesta se puede calcular en tiempo polinomial.
2. Un problema de sí o no está en notario público (norteon-determinista PAGtiempo linomial) si se puede responder sí verificado en tiempo polinomial.

Intuitivamente podemos ver que si hay un problema en PAG, entonces está en notario público.Dada una posible respuesta a un problema en PAG, podemos verificar la respuesta simplemente recalculando la respuesta.

Menos obvio, y mucho más difícil de responder, es si todos los problemas en notario público están en PAG.¿El hecho de que podamos verificar una respuesta en tiempo polinómico significa que podemos calcular esa respuesta en tiempo polinómico?

Hay un gran número de problemas importantes que se sabe que notario público-completo (básicamente, si se demuestra que alguno de estos problemas está en PAG, entonces todo notario público Se ha demostrado que los problemas están en PAG).Si PAG = notario público, entonces se demostrará que todos estos problemas tienen una solución eficiente (tiempo polinómico).

La mayoría de los científicos creen que PAG!=notario público.Sin embargo, aún no se han establecido pruebas de ninguno de los dos. PAG = notario público o PAG!=notario público.Si alguien proporciona una prueba de cualquiera de las conjeturas, ganarán US$1 millón.

Answer 3

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

Supongamos que tenemos un problema que requiere una cierta cantidad de entradas y tiene varias soluciones potenciales, que pueden resolver o no el problema para determinadas entradas.Un acertijo de lógica en una revista de acertijos sería un buen ejemplo:los insumos son las condiciones ("George no vive en la casa azul o verde"), y la solución potencial es una lista de afirmaciones ("George vive en la casa amarilla, cultiva guisantes y es dueño del perro").Un ejemplo famoso es el problema del viajante:Dada una lista de ciudades, y los tiempos para llegar de una ciudad a otra, y un límite de tiempo, una posible solución sería una lista de ciudades en el orden en que las visita el vendedor, y funcionaría si la suma de los viajes veces fue 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 que el vendedor debe visitar en orden, podemos sumar los tiempos de 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 eficientemente una solución, si existe.

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

Por tanto, el problema P=NP se puede expresar de la siguiente 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 esa es la situación actual.Nadie ha podido demostrarlo de ninguna manera, y eso molesta a muchos matemáticos e informáticos.Es por eso que cualquiera que pueda demostrar la solución recibirá un millón de dólares de la Fundación Claypool.

Generalmente suponemos que P no es igual a NP y que no existe una forma general de encontrar soluciones.Si resultara que P=NP, muchas cosas cambiarían.Por ejemplo, la criptografía serí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, de modo que si P = NP podríamos encontrar la clave de manera eficiente sin saberlo de antemano.Descifrar contraseñas se volvería trivial.Por otro lado, hay toda una clase de problemas de planificación y de asignación de recursos que podríamos resolver eficazmente.

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

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

Answer 4

Un breve resumen de mi humilde conocimiento:

Hay algunos problemas computacionales sencillos (como encontrar el camino más corto 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 y k es una constante (en el En el caso 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 u obtener la clave privada RSA de la clave pública, son más difíciles (O(e^n)).

Pero el lenguaje 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 funcionamiento de la máquina tardará mucho).Es decir, tenemos que probar todos los caminos posibles (normalmente los profesores de informática inteligentes pueden excluir algunos).

Es interesante porque nadie tiene 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 sería perjudicial para los cifrados de claves públicas/privadas (como RSA).Podrías romperlos tan fácilmente como lo es ahora generar una clave RSA.

Y es un problema bastante inspirador.

Answer 5

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

Answer 6

Primero, algunas definiciones:

• Un problema particular está en P si se puede calcular una solución en un tiempo menor que n^k para algunos k, dónde n es el tamaño de la entrada.Por ejemplo, la clasificación se puede realizar 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 un k tal que existe una solución de tamaño como máximo n^k que puedes verificar a tiempo como máximo n^k.Tome 3 colores de gráficos:dado un gráfico, una coloración de 3 es una lista de pares (vértice, color) que tiene tamaño O(n) y puedes verificar a tiempo O(m) (o O(n^2)) si todos los vecinos tienen colores diferentes.Por lo tanto, un gráfico se puede colorear con 3 colores solo si hay una solución breve y fácilmente verificable.

Una definición equivalente de NP es "problemas que pueden resolverse mediante norteMáquina de Turing ondeterminista en PAGtiempo olinomio".Si bien eso le indica de dónde viene el nombre, no le brinda la misma sensación intuitiva de cómo son los problemas NP.

Tenga en cuenta que P es un subconjunto de NP:Si puedes encontrar una solución en tiempo polinómico, hay una solución que se puede verificar en tiempo polinómico; simplemente verifica que la solución dada sea igual a la que puedes encontrar.

¿Por qué la pregunta P =? NP ¿interesante?Para responder a esto, primero es necesario ver qué 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' puedes crear una instancia de L que tenga una solución si y sólo si la instancia de L' tiene una solución.Formalmente hablando, todo problema L' en NP es reducible a l.

Tenga en cuenta que la instancia de L debe ser computable en tiempo polinomial y tener un tamaño polinomial, del tamaño de L';de esa manera, resolver un problema NP-completo en tiempo polinomial nos da una solución en tiempo polinomial para todo Problemas del PN.

He aquí un ejemplo:Supongamos que sabemos que la coloración triple de gráficos es un problema NP-difícil.Queremos demostrar que decidir la satisfacibilidad de 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 los colores 1, 2 y 3.

Para cada arista (u, v), tenga el requisito de que (u_h, u_l)! = (v_h, v_l).Eso es,

not ((u_h and not u_l) and (v_h and not v_l) or ...)enumerando todas las configuraciones iguales y estipulando que ninguna de ellas es el caso.

ANDAl unir todas estas restricciones se obtiene una fórmula booleana que tiene tamaño polinómico (O(n+m)).Puedes comprobar que también se necesita tiempo polinómico para calcular:lo estás haciendo sencillo O(1) cosas por vértice y por arista.

Si puedes resolver la fórmula booleana que hice, también puedes resolver el coloreado de gráficos:para cada par de variables v_h y v_l, sea el color de v el que coincida con los valores de esas variables.Según la construcción de la fórmula, los vecinos no tendrán colores iguales.

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

Sabemos que la coloración triple de gráficos es NP-completa;sin embargo, históricamente hemos llegado a saberlo mostrando primero la integridad NP de la satisfacibilidad del circuito booleano y luego reduciéndola a 3 colorabilidad (en lugar de al revés).