211service.com
¿Qué significa 'P vs. NP' para el resto de nosotros?
Los programadores e informáticos han estado hablando durante la última semana sobre el último intento de resolver una de las preguntas más desconcertantes de la informática: el llamado problema P versus NP.
Vinay Deolalikar, un científico investigador de HP Labs en Palo Alto, CA, publicó su prueba en línea y la envió a varios expertos en el campo el 6 de agosto. Los colegas comenzaron inmediatamente a analizar la prueba en blogs y wikis académicos. Las primeras reacciones fueron respetuosas pero escépticas, y el consenso actual es que el enfoque de Deolalikar es fundamentalmente defectuoso.
Una prueba sólida le haría ganar fama y fortuna a Deolalikar. El Instituto Clay de Matemáticas en Cambridge, MA, ha nombrado a P versus NP como uno de sus problemas del Milenio y ofrece $ 1 millón a cualquiera que proporcione una prueba verificada.
Pero P versus NP es más que un simple rompecabezas matemático abstracto. Busca determinar, de una vez por todas, qué tipos de problemas pueden ser resueltos por computadoras y cuáles no. Los problemas de clase P son fáciles de resolver para las computadoras; es decir, las soluciones a estos problemas se pueden calcular en un período de tiempo razonable en comparación con la complejidad del problema. Mientras tanto, para los problemas de NP, una solución puede ser muy difícil de encontrar, quizás requiriendo miles de millones de años de cálculo, pero una vez que se encuentra, se puede verificar fácilmente. (Imagínese un rompecabezas: encontrar la disposición correcta de las piezas es difícil, pero puede saber cuándo el rompecabezas está terminado correctamente con solo mirarlo).
Los problemas de clase NP incluyen muchos problemas de optimización y coincidencia de patrones que son de gran interés práctico, como determinar la disposición óptima de los transistores en un chip de silicio, desarrollar modelos precisos de pronóstico financiero o analizar el comportamiento de plegamiento de proteínas en una célula.
El problema P versus NP pregunta si estas dos clases son realmente idénticas; es decir, si todo problema de NP es también un problema de P. Si P es igual a NP, cada problema de NP contendría un atajo oculto, lo que permitiría a las computadoras encontrar rápidamente soluciones perfectas para ellos. Pero si P no es igual a NP, entonces no existen tales atajos y la capacidad de resolución de problemas de las computadoras seguirá siendo fundamental y permanentemente limitada. La experiencia práctica sugiere abrumadoramente que P no es igual a NP. Pero hasta que alguien proporcione una prueba matemática sólida, la validez de la suposición permanece abierta a dudas.
Incluso si se determinara que la prueba de Deolalikar es sólida, la pregunta sigue siendo: ¿qué impacto tendría dicha prueba en áreas relevantes de la informática?
Superficialmente, uno podría pensar que la respuesta no es mucha. Demostrar que P no es igual a NP simplemente confirmaría lo que casi todo el mundo ya asume que es cierto a efectos prácticos, explica Scott Aaronson , investigadora de complejidad en el Laboratorio de Ciencias de la Computación e Inteligencia Artificial del MIT.
Por ejemplo, nuestra incapacidad para factorizar de manera eficiente números compuestos enormes (un problema clásico de NP) forma la base de la criptografía moderna, que sustenta todo, desde la seguridad nacional hasta las compras de Amazon.com. No necesitamos una prueba formal de que P no es igual a NP para basarnos en la conjetura, dice Aaronson. Los programadores conocen el problema y estarían emocionados de ver que P no es igual a NP probado, pero en el día a día, saben que reformular [un problema de NP] en algo más fácil tiene mucho más sentido que tratar de resolver el problema matemático. problema del siglo.
Debido a que los problemas de clase NP son tan generalizados (incluso los sudoku y las búsquedas de horarios de aerolíneas en Bing.com son difíciles de calcular), constantemente se descubren soluciones alternativas innovadoras. La optimización estocástica, por ejemplo, imita la aleatoriedad que se encuentra en los sistemas físicos (como los metales refrigerantes o la mutación del ADN) para producir soluciones suficientemente buenas en lugar de soluciones computacionalmente difíciles.
Los intentos de hacer frente a la suposición de que P no es igual a NP nos ayudan a desarrollar nuevas tecnologías mentales, dice Richard Lipton , científico informático de Georgia Tech que estudia el problema P versus NP. A pesar de que hemos estado escribiendo algoritmos durante décadas, no comprendemos completamente de qué son capaces, continúa. Entonces, incluso si probaras que P no es igual a NP, algo en lo que todos ya creen, tendríamos que expandir radicalmente nuestra comprensión de esas capacidades y hacer posibles muchas cosas nuevas con las computadoras, además de todas las soluciones inteligentes que ya tenemos. fundar.
Entonces, si el progreso incremental aún puede generar una innovación útil, ¿por qué no son los titanes de la investigación industrial como Google, Microsoft y HP (quienes se negaron a comentar para este artículo) dedicar enormes equipos de investigadores al rompecabezas P no es igual a NP? Demostrar un resultado negativo es increíblemente difícil y, desde el punto de vista [de una gran empresa], probablemente no tenga mucho impacto en el próximo trimestre financiero o incluso en los próximos años de su negocio, dice Lipton. Es más un problema a largo plazo.
Por supuesto, siempre existe la alternativa: demostrar que P lo hace de hecho es igual a NP. Pero no contenga la respiración, dice Aaronson. Hay buenas razones por las que muy pocas personas creen que P es igual a NP, dice. Si fuera así, estaríamos viviendo en un universo fundamentalmente diferente, y probablemente ya nos habríamos dado cuenta.