Las implicación práctica de P vs NP problema

Question

Aunque si $$ P = NP $$ que es importante de la informática teórica punto de vista, pero no veo ninguna implicación práctica de esto.

Supongamos que podemos probar todas las preguntas que se pueden verificar en el polinomio tiempo han polinomio soluciones de tiempo, que no nos ayudará en la búsqueda de las soluciones actuales. Por el contrario, si podemos probar que $$ P \ne NP,$$, a continuación, esto no significa que nuestro actual NP-hard problemas no tienen polinomio tiempo de soluciones.

Desde el punto de vista práctico ( práctica como en el sentido de que podemos utilizar inmediatamente la solución para ejemplo del mundo real), no me molesta si P vs NP es probar o refutar más que si mi problema tiene una solución en tiempo polinomial.

Estoy en lo cierto?

Answer 1

Muchos de los problemas que tenemos que saber para estar en NP ni NP-completos son los problemas que en realidad queremos resolver, los problemas que se plantean, por ejemplo, en el diseño de circuitos o en otras solicitudes de diseños industriales. Además, dado que las diversas NP-completos son problemas de todos polinomio relacionados con el tiempo el uno al otro, si deberíamos aprender un medio factible para la solución de alguno de ellos, tendríamos medio viable para todos ellos. El resultado de esto sería extraordinario, algo así como una segunda revolución industrial. Es como si de repente había un enorme aumento permanente de la potencia de cálculo, lo que nos permite resolver una enorme variedad de problemas prácticos hasta ahora fuera de nuestro computacional llegar. El P vs NP pregunta es importante, en parte debido a esta tentadora posibilidad.

Si fuera probado que P = NP y la prueba proporciona un determinado polinomio tiempo algoritmo para NP-completos problema, debido a la reducción de las pruebas, se podría presentar de inmediato el polinomio de algoritmos en tiempo para todos nuestros favoritos NP problemas. Por supuesto, una prueba puede ser indirecta, y no proporcionar un determinado polinomio algoritmo de tiempo, pero usted puede estar seguro de que si tenemos una prueba de que P=NP, entonces los enormes recursos que se ponen en la extracción de la prueba de un speciffic algoritmo.

Por el contrario, si alguien se prueban $P \neq NP$, entonces significaría que no podría haber ningún polinomio tiempo de solución para cualquier NP problema completo. (En particular, la última frase de su párrafo segundo, no es correcto.)

Answer 2

Si $P = NP$, computacional revolución (una vez que un algoritmo específico es identificado por un NP-duro problema, con explícita asintótica de tiempo de ejecución de los límites).

Si $P < NP$ y se puede demostrar que, seguro (clásica) de la criptografía seguramente existe, y una enorme pieza que faltaba en nuestra comprensión de la computación se llena. La primera ya tiene importantes implicaciones para la vida diaria, y el desarrollo de la segunda tendría implicaciones mucho mayores.

También debe entender que después de 40 años de investigación, hoy en día P=NP lleva a un host de ideas relacionadas como: de fácil a difícil transición de fase en problemas de combinatoria; cuantificables límites entre fácil y difícil aproximado versiones específicas del tipo NP-completo los problemas (por lo que conseguir dentro de 7/8 de la solución óptima es fácil, pero nada más cercana es NP-completo); contar al azar y el muestreo de objetos combinatorios son el mismo problema; cero-conocimiento de pruebas ", que revelan nada, pero su propia validez" (unforgeable tarjetas de IDENTIFICACIÓN). Es un universo muy rico de ideas y que no se acabe de preguntas una vez que usted sabe la respuesta a P=NP.

Answer 3

En realidad $P \ne NP$ no significa que nuestro actual NP-hard problemas no tienen los polinomios de soluciones de tiempo. NP-completos, los problemas son los más difíciles problemas en NP y NP-hard problemas son al menos tan duro como este. Así que si $P \ne NP$, entonces todas estas NP-duro de problemas debe ser más difícil que en P.

Si la prueba nos ayuda a encontrar soluciones dependerá, naturalmente, de la prueba. Si $P \ne NP$, entonces sabemos que no pierdas el tiempo buscando el polinomio de soluciones.

Si $P=NP$, a continuación, los verdaderos beneficios de la práctica sería, por supuesto, vienen de la solución, en lugar de la prueba. Eso está muy bien - no hay ninguna razón por la que todos los teóricos de ciencias de la computación debe ser directamente práctico.

Answer 4

No relacionados directamente con la pregunta, pero sin duda relevante.

Hace tres días de prueba para P! = NP se publica. Comunidad piensa que parece grave.

Answer 5

En la actualidad, si un gerente le pide a su equipo de ingeniería de software para mirar a la aplicación de alguna utilidad, y el equipo dice que los requisitos son NP duro, esa es una razón por la que el proyecto requisitos deben ser cambiadas antes de que los trabajos sobre la aplicación puede comenzar. Eso es porque nadie sabe cómo dar posibles soluciones a dichos problemas.

La pluralidad de los teóricos de la complejidad, además, cree que P =/= NP, lo que significa que hay una creencia generalizada entre los expertos de que las soluciones posibles a estos problemas nunca será encontrado.

Si alguien muestra P=NP, entonces, si el equipo dice que los requisitos son NP-completo, entonces el director y el equipo va a comenzar a dejar de hablar de la teoría de las posibles realizaciones y de su eficacia.