Problemáticas actuales en la Computación
Desde el año 2000 está pendiente el destino de los 7 millones de dólares prometidos por el Instituto Clay a quienes resuelvan los 7 Problemas del Milenio. Mientras, la comunidad matemática reparte sus fondos entre los que inventan más conjeturas.
En agosto pasado el congreso de la Unión Matemática Internacional, celebrado en Corea del Sur, galardonó con su premio anual al profesor del Instituto Courant de Ciencias Matemáticas de Nueva York Subhash Khot. El científico de origen indio dedicó mucho tiempo a la teoría de la complejidad computacional, el primero de los siete retos. Sin embargo, no demostró el teorema existente al respecto, que lleva los nombres de los matemáticos Cook y Levin, sino que ofreció una nueva conjetura, motivo por el cual fue premiado por el jurado.
¿Cuál es el enigma que vale un millón y cuesta tantos esfuerzos? Los matemáticos no solo lo reproducen en fórmulas científicas, sino que las plantean como si fuera una situación cotidiana.
1. P contra NP
Supongamos que usted se encuentra en un salón junto con muchas otras personas y quiere saber si su amigo también está ahí. Si les dicen que está sentado en el rincón contrario de la sala bastará un instante para verificar la información. A falta de esa información, sin embargo, usted tendrá que recorrer el salón una y otra vez y mirar a todos los invitados hasta encontrar a su amigo. Eso demuestra que solucionar un problema lleva más tiempo que verificar una solución ya ofrecida.
¿Pero es la misma la respuesta en los modelos matemáticos, y en especial en la informática? Aparentemente sí, pero nadie ha podido comprobarlo con suficiente veracidad.
El investigador Stephen Cook planteó el problema de la siguiente manera: ¿verificar una solución es más difícil y lleva más tiempo que obtener una solución propia independientemente del algoritmo de la verificación? Cook formuló esta pregunta en 1971 como el problema de las clases de complejidad P y NP y desde entonces la cuestión sigue sin resolver, a pesar de la gran importancia que tiene para la informática. Los especialistas dicen que resolver la cuestión podría revolucionar las bases de la criptografía que se usa para la transmisión y el almacenamiento de datos, y en particular para la mensajería electrónica segura y sistemas de pago como el bitocóin.
2. Hipótesis de Riemann
Algunos números naturales no tienen ningún divisor aparte de sí mismos y el 1. Estos números son 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, etc. Se llaman números primos y desempeñan un importante papel en la matemática pura y sus aplicaciones. Según los manuales escolares, la distribución de estos números en el conjunto de los números naturales enteros no obedece ninguna lógica. Sin embargo, el alemán Bernhard Riemann supuso que existe una función matemática para esta consecuencia que se calcula mediante la denominada 'función zeta', que describe la distribución de los 'ceros no triviales'.
El propio autor de la conjetura no pudo predecir la transcendencia informática de sus ideas. Pero actualmente sí se espera que, una vez comprobada, la hipótesis tenga un impacto revolucionario sobre los métodos de codificación y la seguridad de Internet.
En el año 2004 Xavier Gourdon verificó la conjetura de Riemann numéricamente a lo largo de los primeros diez trillones de ceros no triviales de la función. Sin embargo, la comunidad matemática concluyó que no se trataba estrictamente de una demostración.