este artículo apareció originalmente en Motherboard Germany. Desde su publicación original se ha actualizado con nueva información por Motherboard US. ¿Qué tienen en común el cáncer curable, el capitalismo justo y el juego perfecto de Super Mario Bros? Según una teoría matemática, la solución a cualquiera de estos problemas nos permitiría resolver rápidamente los demás., Todo lo que se necesita son mejores algoritmos para demostrar que las preguntas complicadas, como el plegado de proteínas, los mercados eficientes y los análisis combinatorios, son simplemente variaciones de problemas más simples que las supercomputadoras ya son capaces de resolver. Pero, ¿cómo puede un algoritmo simplificar problemas extremadamente complicados? Eso depende de otra pregunta: ¿Qué pasa si los problemas complicados son realmente problemas simples disfrazados?, Este acertijo sigue siendo una de las mayores preguntas sin resolver de las matemáticas modernas, y es uno de los siete problemas del Premio del Milenio, por el cual cada respuesta aceptada es recompensada con un millón de dólares.
Ahora, un hombre alemán llamado Norbert Blum ha afirmado haber resuelto el anterior acertijo, que es bien conocido como el P vs NP problema. Desafortunadamente, su supuesta solución no tiene buenas noticias., Blum, que es de la Universidad de Bonn, afirma en su artículo de 38 páginas recientemente publicado que P no es igual a NP. En otras palabras, los problemas complicados son fundamentalmente diferentes de los problemas sencillos y no parece que nuestras computadoras de alto rendimiento puedan resolver estos problemas más difíciles en un futuro cercano. Y en los días desde que se publicó su artículo, numerosos matemáticos han comenzado a plantear preguntas acerca de si Blum resuelto en absoluto.
¿Qué es exactamente el problema P versus NP?,
La mayoría de los científicos informáticos tienden a estar de acuerdo con la conclusión de Blum. Los problemas difíciles son difíciles, los problemas fáciles son fáciles. En Ciencias de la computación, los problemas fáciles generalmente caen bajo la bandera de P. Esto significa que se pueden resolver en «tiempo polinómico», que es muy parecido a decir que se pueden resolver en un período de tiempo razonable. Mucho más difíciles son los problemas de NP, que las computadoras no pueden resolver en un marco de tiempo razonable. Para fines prácticos, los problemas de NP también podrían ser irresolubles para las computadoras., (Tenga en cuenta, sin embargo, que NP significa «tiempo polinómico no determinista» en lugar de tiempo «no polinómico». Estos son algunos ejemplos de problemas de NP:
plegamiento de proteínas: el proceso a través del cual las proteínas en un organismo biológico obtienen su estructura. Una mejor comprensión de este proceso podría ayudarnos a reconocer o incluso dificultar las mutaciones, que podrían curar ciertas formas de cáncer. Búsqueda de rutas optimizada: ¿una ruta de viaje optimizada a través de 15 ciudades diferentes sin visitar la misma ciudad dos veces?, Una tuerca difícil de romper, incluso para una supercomputadora, por lo que esto también se considera un problema de NP en Ciencias de la computación.
El perfecto juego de ajedrez: Un juego de ajedrez tiene una infinidad de movimientos posibles, de tal forma que incluso una supercomputadora con capacidad increíble no puede determinar una táctica perfecta. Muchos matemáticos consideran este problema tan difícil que no lo consideran un problema de NP, sino que lo consideran completamente fuera del ámbito de la posibilidad.,
todos estos problemas complejos tienen una cosa en común: por difícil que sea encontrar una solución a los problemas de NP, es relativamente fácil verificar la validez de las soluciones una vez que las tiene.
estas dos distinciones categóricas en la complejidad de los problemas tienen orígenes antes del surgimiento social de las computadoras domésticas. En la década de 1970, cuando las computadoras todavía eran del tamaño de una nevera torpe, se determinó rápidamente que no todos los problemas de la humanidad podrían resolverse simplemente con esas máquinas., Se propuso que la distinción podría formalizarse en términos de complejidad computacional, dando lugar a un conjunto de clases de complejidad, incluidas N y NP.
desde la definición formal de P y NP en 1971, los científicos de la computación han debatido si sería posible o no llegar a un algoritmo capaz de reducir o redefinir los problemas de NP de modo que puedan ser resueltos en tiempo polinómico. Si alguien pudiera probar que todos los problemas de NP son en última instancia solo variaciones de los problemas de P, entonces todos los problemas de NP estarían esencialmente sujetos a la misma forma de reducción., En otras palabras, quien conozca la táctica perfecta de Super Mario Bros. también podría curar el cáncer.
En total, 116 de los más valientes en su campo oficialmente han intentado resolver este misterio (aunque incalculables más científicos de la computación han publicado que sería soluciones a messageboards y en sitios como arXiv). Hasta la fecha, ninguna de estas pruebas ha sido reconocida oficialmente por la comunidad matemática.
Una Especie de ¿Quién Quiere ser Millonario?, para matemáticos
en 2000, el Instituto de matemáticas de arcilla (CMI), ubicado en Oxford, compiló una lista de siete problemas no resueltos del Premio del Milenio, prometiendo un millón de dólares por cada solución. Es una especie de ¿Quién Quiere ser Millonario? o X Premio para matemáticos. Los problemas del Premio del Milenio se consideran excepcionalmente difíciles incluso en los círculos de expertos. Se necesita una gran cantidad de conocimientos específicos del campo para comprender incluso las preguntas., El único problema del Premio del Milenio resuelto hasta la fecha es la conjetura de Poincaré, que no se explica fácilmente como un apartado en un artículo sobre un concepto matemático diferente.
resolver el problema de NP no sería algo del todo bueno. Por ejemplo, la mayoría del cifrado se basa en la dificultad de factorizar números primos muy grandes. La factorización de enteros es un problema de clase NP. Un código de 256 bits, como los que utilizan las instituciones financieras en los pagos con tarjeta de crédito en línea, se considera irrompible y, por lo tanto, muy seguro., Si alguien demuestra que NP es igual a P, Los bancos tendrían que idear rápidamente un método de seguridad diferente.
¿qué piensan los matemáticos de la prueba matemática de Blum?
desde que se publicó el artículo de Blum, matemáticos y científicos informáticos de todo el mundo han estado devanando sus cerebros en cuanto a si el investigador con sede en Bonn, de hecho, ha resuelto este problema del Premio del Milenio. Después de una reacción inicialmente positiva, como la del matemático de Stanford Reza Zadeh, comienzan a surgir dudas sobre si el razonamiento de Blum es correcto.,
en un foro de matemáticas teóricas, un usuario llamado Mikhail se acercó a Alexander Razborov-el autor del documento en el que se basa la prueba de Blum—para preguntarle sobre el documento de Blum. Razborov pretende haber descubierto un error en el documento de Blum: el argumento principal de Blum contradice una de las suposiciones clave de Razborov. Y el matemático Scott Aaronson, que es algo así como una autoridad en la comunidad matemática cuando se trata de P vs., NP, dijo que estaría dispuesto a apostar 2 200,000 que la prueba matemática de Blum no perdurará. «Por favor, deja de preguntar», Escribe Aaronson. Si la prueba no ha sido refutada, «puedes volver y decirme que fui un tonto de mente cerrada.»En la semana desde la entrada inicial del blog de Aaronson, otros matemáticos han comenzado a tratar de hacer agujeros en la prueba de Blum. Dick Lipton, profesor de Ciencias de la computación en Georgia Tech, escribió en un blog que la prueba de Blum «pasa muchos filtros de seriedad», pero sugirió que puede haber algunos problemas con ella., Un comentarista en esa entrada de blog, conocido solo como» vloodin», señaló que había un» único error en un punto sutil » en la prueba; otros matemáticos han intervenido y confirmado el análisis inicial de vloodin, por lo que el consenso emergente entre muchos matemáticos es que una solución para P vs.NP sigue siendo esquiva. Traducido por Melina McCormack.