Motherboard publicó que un hombre, Norbert Blum, podría haber resuelto el problema P≠NP. Intentaremos explicar la importancia de este hecho a continuación.
Hay muchísima información que digerir para empezar a entender el problema P≠NP, pero básicamente la solución demuestra el poder potencial de las computadoras. Para nosotros los legos, el poder de cómputo parece infinito. Seguramente con suficiente poder de procesamiento y tiempo podríamos calcular cualquier cosa ¿cierto? No exactamente.
Desde 1971, los científicos computacionales encontraron que hay básicamente dos diferentes tipos de problemas según su complejidad. Los problemas tipo P son problemas sencillos, cosas que las computadoras pueden resolver con suficiente poder de cómputo en una razonable cantidad de tiempo. ¿Recuerdas la primera vez que multiplicaste 1 000 000 por 1 000 000 en una calculadora? Ese es un problema tipo P.
Los problemas tipo NP no se pueden resolver mediante algoritmos computacionales sin importar el poder de cómputo disponible ni el tiempo. Cosas como calcular la partida perfecta de Mario Bros (no es broma, si hay gente intentándolo), movimientos perfectos de ajedrez, o plegamiento de proteínas son problemas NP.
Los matemáticos y científicos de la computación descubrieron que un montón de problemas NP son irresolubles de las mismas formas, las puertas son diferentes pero las cerraduras son iguales. Si tan solo pudiéramos encontrar las llaves. Ésta es la dificultad. ¿Cómo saber si los problemas NP son en realidad problemas P para los que todavía no encontramos el truco o si realmente son cosas que nunca seremos capaces de computar?
Así que, de vuelta al tema, Blum supuestamente encontró que P no es igual a NP. De acuerdo a su solución: hay algunos problemas que simplemente nunca seremos capaces de computar. Y eso puede que sea una buena cosa.
La mayor parte de nuestros sistemas de encriptación están basados en la dificultad de factorizar números primos muy largos. La factorización de enteros es un problema de clase NP. Un código de encriptación de 256 bits, como el que usan los bancos e instituciones financieras para proteger la información de nuestras tarjetas de crédito en línea se considera irrompible. Por lo tanto seguro. Si alguien demostrase que los problemas NP son, de hecho, problemas P disfrazados… los bancos tendrían que encontrar una nueva solución de seguridad. Pronto.
El asunto es que P≠NP o “P vs NP” es un problema de los que el Clays Mathematics Institute (CMI) denominó “problema del Milenio” junto con otros 6 problemas y establació un premio de Un Millón de Dólares para quien presentara una solución. Hasta el momento, el único problema del milenio resuelto es la Conjetura Poincaré.
De todas formas y como siempre en la ciencia (principio de falsabilidad): el resto de los matemáticos entablaron una aguerrida competencia para demostrar que Blum estaba equivocado y… Lo lograron. Blum ya se ha retractado y lo ha publicado.
La prueba es errónea. Debo establecer con precisión cuál es el error. Para hacer esto necesito algo de tiempo. Pondré la explicación en mi página.
Así pues, ese problema de comunicación que tienes (y el pago de la tanda en la oficina), no es el único problema sin solución para siempre.
Al menos por el momento.
