¿Por qué es P vs NP un problema importante para resolver?

El problema es que una prueba de P = NP puede no proporcionar ninguna pista sobre cómo construir o encontrar los algoritmos para realmente colapsar NP en P no tendrá ningún impacto práctico y, por lo tanto, en este sentido no es importante, ya que fue sinceramente No es importante la prueba del teorema de Fermat, especialmente porque una pregunta aritmética requería una respuesta del análisis matemático, e incluso ZFC (cf abajo), matando una mosca con un canon. Que hacer matemáticas por el bien de la ciencia en el futuro lejano es una gran exageración.

Pero volviendo a la pregunta, para mí solo hay 2 posibilidades más probables para la pregunta P =? NP. O P =! NP, o P = NP está probado, pero en la práctica no hay forma de encontrar los algoritmos para hacer que cada problema en NP sea un problema en P. Esto es realmente por qué algunos de nosotros pensamos que la pregunta puede estar mal planteada porque la suposición subyacente es que P =? NP es muy relevante en la práctica (por ejemplo, descifrar algoritmos basados ​​en funciones unidireccionales como el cifrado RSA), pero en realidad es muy probable que sea irrelevante en la práctica.

Por ejemplo, una prueba teórica no constructiva puede colapsar todas las clases de complejidad, pero en la práctica pueden sostenerse porque el algoritmo en P es demasiado difícil en la práctica (como en teoría también debería estar en P si P = NP) para encontrar, si no es imposible, o en última instancia, existen restricciones físicas (por ejemplo, un argumento termodinámico) a lo que realmente puede hacer, especialmente si una prueba no constructiva no proporciona los medios para producir el algoritmo en P para uno previamente conocido en NP. Por el contrario, si es poco probable como lo creo, no solo P = NP, sino que encontramos una manera de encontrar el algoritmo en P para cualquier problema que se crea en NP, entonces el impacto será enorme para todas las áreas de la ciencia y la tecnología.

En realidad, es bastante simple ver cómo una prueba para P = NP puede no implicar nada. Esto es cambiando el marco estándar de cálculo. Ha habido, por ejemplo, sugerencias que tiene P = NP. Sin embargo, las pruebas que muestran esto hacen uso de formas de cómputo no estándar que están etiquetadas con el nombre místico de ‘hipercomputación’, es decir, el uso de cierto tipo de computadoras con capacidades extraordinarias, como ser arrojado a un agujero negro y a la computadora aún funciona y le devuelve los resultados de un cálculo, o una computadora que puede calcular más rápido de lo que permite la termodinámica, y así sucesivamente. Puede pensar entonces que tales modelos ‘divertidos’ obviamente deberían estar prohibidos, sin embargo, si se acerca a P = NP desde el punto de vista puramente matemático, los matemáticos cambian sus marcos todo el tiempo (especialmente cuando buscan probar teoremas a toda costa , por ejemplo, forzar), incluso haciendo uso común de sistemas axiomáticos no constructivos / no compatibles (o se sospecha que lo es si no tiene una computadora con propiedades extraordinarias como las que acabo de describir), como Set Theory con el Axioma de elección (un axioma que te permite elegir un elemento de un número infinito de conjuntos, algo, en la práctica, imposible) llamado ZFC.

Por lo tanto, las teorías matemáticas que requieren este tipo de poder ‘infinito’ también son no construibles / no computables y son muy comunes hasta el punto de que los matemáticos rara vez preguntan el marco en el que se ha demostrado un teorema cuando quieren reutilizarlo para algo más. Tampoco siempre está claro qué otros sistemas de axiomas matemáticos, por ejemplo, algunas formas de cálculo (análisis matemático), necesitan toda la potencia de ZFC (la mayoría de las teorías matemáticas lo hacen), por lo que en la práctica, incluso algunos teoremas que se consideran ‘ se demostró que ‘puede estar usando este tipo de’ truco ‘que en teorías construibles / computables, como las sugeridas para P = NP, uno diría inmediatamente que no deberían permitirse. Sin embargo, al final, incluso ese tipo de matemática resulta ser extremadamente útil, incluso en tareas muy constructivas como la práctica de la ingeniería y la tecnología, incluso si las teorías en sí mismas no son construibles.

Entonces, ahora puede ver el problema, si la pregunta de P = NP no siempre viene con el marco esperado en el que desea que sea cierto o no, o las condiciones para las que desea que se demuestre o refute. Y es el caso de que el marco implícito de la pregunta es el modelo de cálculo de Turing, pero parece que el marco está incompleto si no incluye el tipo de condiciones más precisas que cuantifican si la respuesta realmente puede producir los algoritmos en P para todos los problemas previos en NP, o si se puede permitir una prueba puramente no constructiva, por ejemplo, utilizando sistemas de axiomas generales, empujando la pregunta P =? NP a la irrelevancia en la práctica, ya que estaría desconectada del sentido mismo (de factibilidad) en que se hizo la pregunta.

Respetuosamente estoy en desacuerdo con las respuestas que dicen que no es importante. El problema P vs NP es el problema más profundo en la informática teórica, y uno de los cinco principales en lógica matemática.

Su importancia no se deriva de ninguna implicación práctica inmediata. Como la mayoría de los otros problemas de las matemáticas puras, no lo buscamos porque esperamos que surjan algunos dispositivos tecnológicos. No investigamos la hipótesis de Riemann por razones prácticas, ni la conjetura de Birch y Swinnerton-Dyer, ni P vs NP.

¿Es “importante” resolver problemas que profundizan nuestra comprensión del universo matemático? Puede sentir que es así, o puede sentir que no lo es. Es un juicio de valor. La historia muestra que muchos desarrollos (ciertamente no todos) en matemática pura finalmente encuentran aplicaciones prácticas, pero esta no es la verdadera motivación que buscan muchos matemáticos. Si define “importante” como “que tiene relevancia tecnológica directa”, entonces P vs NP es poco probable que sea un problema importante.

Pero si acepta que las matemáticas puras son una búsqueda humana fundamentalmente importante, entonces sería difícil encontrar muchos problemas que excedan P vs NP en centralidad e importancia. NP es una clase muy natural de problemas, y identificar si todos los problemas en NP se pueden resolver de manera eficiente es como preguntar si las pruebas matemáticas son tan fáciles de encontrar como de verificar, o si la mayoría de las cosas se pueden resolver La fuerza bruta también se puede resolver de manera más elegante y eficiente. Es una pregunta básica sobre la naturaleza de la resolución de problemas, la computación y, de hecho, la investigación matemática misma.

No creo que tengamos una comprensión real de la complejidad computacional y una de las áreas en las que, al menos para mí, esto brilla en preguntas como P = NP.

‘El problema P versus NP es un gran problema no resuelto en informática. Hablando informalmente, pregunta si cada problema cuya solución puede ser verificada rápidamente por una computadora también puede resolverse rápidamente por una computadora ”.

Ahora, ¿qué demonios podría significar esto?

Supongamos que se me ocurre un algoritmo novedoso que puede resolver el problema del vendedor ambulante para cualquier número de ciudades que desee en un tiempo constante, por ejemplo, la edad del universo.

Ahora eso es bastante impresionante al no necesitar ni siquiera tiempo polinómico, pero ¿qué pasa con la constante? Es el término constante que, al menos en este caso, mata el algoritmo. Uno no puede simplemente ignorarlo.

Escandalosamente diría que no lo es, ya que se cree que P ! = NP . Si esto se mostrara, las expectativas funcionarían normalmente. Su cifrado RSA de 2048 bits desde el cajero automático a los servidores del banco seguiría siendo “difícil” de romper, es decir, ningún algoritmo de tiempo polinómico podría descifrarlo fácilmente. La vida continuaría. Los esfuerzos se concentrarían por completo en encontrar algoritmos para problemas de NP con constantes y potencias cada vez más bajas, como la multiplicación de matrices (la multiplicación ingenua toma [matemáticas] O (n ^ 3) [/ matemáticas] pero con cosas como el algoritmo de Strassen, esto ha llegado abajo a [matemáticas] O \ izquierda (n ^ {2.81} \ derecha) [/ matemáticas]).

Sin embargo, si se demostrara, sucederían todo tipo de cosas horrendas. El problema del vendedor ambulante tendría una solución fácil. El cifrado WPA podría romperse sin importar cuán grande sea la clave, en tiempo polinómico. Sus cajeros automáticos no serían seguros. Muy buenas técnicas traerían mejoras masivas a campos como los gráficos de computadora (y, por lo tanto, los videojuegos) si pudiéramos encontrar un algoritmo de multiplicación de matriz polinómica, por ejemplo.

Entonces, esa es la esencia de la pregunta del millón de dólares que vale mucho más que un millón de dólares.

El problema P versus NP ha aparecido en programas como The Simpsons y Numb3rs, y en el videojuego SIMS 3. ¿Cuál es el problema P versus NP y por qué debería importarnos?

El jueves pasado (12 de septiembre) en la serie de conferencias Math for Everyone, Lance Fortnow, profesor y presidente de la Facultad de Ciencias de la Computación del Instituto de Tecnología de Georgia, hizo una presentación sobre la importancia del problema P versus NP y cómo, Si se resuelve, podría afectar dramáticamente nuestra vida cotidiana.

Fortnow exploró la historia y la importancia del problema P versus NP utilizando varios ejemplos no técnicos, uno de los cuales era una mano robótica. A lo largo de la conferencia, Fortnow usó la mano robótica como una metáfora para demostrar cómo P ≠ NP representa problemas que no se pueden resolver. Aunque sabemos cuál debería ser la solución a un problema, que en este caso sería crear una mano robótica similar a la humana, la solución para crear una mano robótica similar a la humana completamente funcional no se puede cumplir por completo.

Lance Fortnow

Ahora, si P = NP, podríamos encontrar soluciones a los problemas de búsqueda tan fácilmente como verificar si esas soluciones son buenas. Esto resolvería esencialmente todos los desafíos algorítmicos que enfrentamos hoy y las computadoras podrían resolver casi cualquier tarea. Usando el ejemplo de Fortnow, si P = NP, entonces la mano robótica sería capaz de hacer cualquier cosa que una mano humana real pueda hacer. Si pudiéramos encontrar la solución para mostrar que P = NP, podríamos ayudar a curar enfermedades como el cáncer y revolucionar la sociedad.

El Clay Mathematics Institute (CMI) de Cambridge, Massachusetts, estableció siete problemas de premios, uno de los cuales es el problema P versus NP. La Junta Directiva de CMI designó un fondo de premios de $ 7 millones para la solución de estos problemas, con $ 1 millón asignado a la solución de cada problema.

Fortnow también ha publicado un libro sobre el problema P versus NP, llamado P, NP y la Búsqueda de lo imposible .

Estoy de acuerdo con Andrew Taylor: en realidad no es tan importante. Las probabilidades son abrumadoras de que P! = NP. Todos proceden como si fuera el caso. En realidad, probarlo provocaría la inundación habitual de preguntas de Quora: “¿Qué cambios?” “Nada.” “¿Entonces no hay autos voladores?” “No.”

Sería notable si no fuera cierto, y mucho cambiaría, al menos potencialmente. Eso lo pone a la par con la investigación antigravedad: sí, sería genial si lo tuviéramos, pero no lo haremos. Y ciertamente no lo encontraremos en ningún lugar obvio en el que pueda golpear en su garaje, porque todos ya han mirado allí. Tal vez hemos pasado por alto algo. Pero no lo hemos hecho.

No sé por qué atrae tanta atención, ya que el 90% de las personas que escucho hablar sobre eso en realidad no saben lo que significa el N en NP. Básicamente, llama la atención porque al menos en la superficie suena simple, y la gente escuchó que hay algún tipo de juju mágico allí, por lo que la fama y la fortuna son tuyas solo por la simple tarea de hacer lo que todos los demás han fallado.

Así que los investigadores reales prácticamente no le prestan atención. De vez en cuando pueden jugar con él, pero sin una idea real de cómo hacerlo, nadie se molesta por mucho tiempo. Me imagino que se probará uno de estos días, probablemente como la prueba de Wiles del último teorema de Fermat: largo, aburrido y de poco interés para cualquier persona fuera del campo, excepto para saber que el problema no resuelto está resuelto, y nada más.

Como solucionador de P vs NP, en realidad leí este hilo y lo encontré útil, ya que mi enfoque para resolver P vs NP se ha autofinanciado y dependía de la información y las bibliotecas disponibles gratuitamente.

Creo que el artículo de Lance Fortnow en CACM, septiembre de 2009, ofrece una gran encuesta de enfoques, usos e historia de cómo surgió este problema y cómo puede dar forma a las industrias.

Sin embargo, la inclinación de Lance está sesgada hacia P = NP

Para encontrar aplicaciones de P! = NP, las aplicaciones especialmente beneficiosas también resultaron ser bastante desafiantes y aterradoras.

Ahora estoy menos aterrorizado y más feliz. Estoy trabajando en un Resumen Ejecutivo cuya declaración de misión incluye “cura para la diabetes usando técnicas de prueba P vs NP”