Gustavo Valenzuela
Ingeniería Matemática.
El Instituto Clay de
Matemáticas de Cambridge, Estados Unidos, está dispuesto a premiar con un
millón de dólares a quien halle una solución a uno de los siete Problemas del
Milenio, lista de problemas matemáticos formulada por dicha institución en el
año 2000. De estos problemas, uno es probablemente el más importante en la
actualidad debido a las consecuencias que traería a muchas áreas de
investigación, a la industria y a la seguridad de datos, tanto positivas como
negativas: P vs NP.
En ciencias de la
computación, P y NP corresponden a dos clases de complejidad que categorizan a
los problemas de decisión en base al tiempo en que estos pueden ser resueltos
mediante un algoritmo. En P se encuentran los problemas para los cuales es
posible encontrar una solución en un tiempo del tipo polinomial, que en
términos de esta ciencia se considera como un tiempo eficiente o razonable de
resolución. En cambio, en NP se encuentran los problemas que, dada una solución,
esta se puede verificar en un tiempo del tipo polinomial. Se sabe que P está
contenido en NP, es decir, si un problema es resoluble en un tiempo razonable,
también es verificable su solución en dicho tiempo. El problema está en
demostrar si existe una doble contención, esto es, si a un problema fácilmente
verificable es posible hallarle un algoritmo que permita resolverlo fácilmente.
¿Por qué es tan
importante esto? La razón está en que este problema permite visualizar los
límites de la computación. “Alan Turing ya había definido décadas atrás qué
pueden resolver los ordenadores y qué no en términos absolutos. Pero sucede que
«hay problemas que sí pueden ser resueltos por un ordenador, solo que la
máquina tardaría tanto que el Sol moriría antes», señala Cook”
(Extracto de bbva.com).
Si P y NP son
equivalentes, cualquier problema matemático puede ser resuelto fácilmente
empleando un computador, puesto que, sin importar su aparente dificultad,
existe un algoritmo que aborde dicho problema de una manera eficiente. Entre
las primeras consecuencias que traería una respuesta afirmativa a dicho problema
sería la obsolescencia de muchos códigos de seguridad informática. La
criptografía se aventaja del hecho de que existen funciones con soluciones
sencillas, pero para las cuales hallar una solución de su inversa es increíblemente
difícil. Muchas cuentas de seguridad, correos, e incluso, claves de tipo
bancario hacen uso de estas funciones asimétricas y otras herramientas para
asegurar una protección robusta de los datos. En un mundo donde P y NP son
equivalentes, es posible dar con un algoritmo que “rompa” esta seguridad o
halle la combinación adecuada de alguna clave en un tiempo breve. Por otra parte,
el mundo de las matemáticas y las ciencias entraría en una nueva fase de
mayores avances en muchos problemas e investigaciones que se están realizando,
dado que podrían abordarse computacionalmente, hallando métodos de resolución a
problemas que parecían intratables. En caso contrario, si P no fuera igual a
NP, quedaría demostrado que no existe un buen algoritmo para todo problema, lo
que motivaría a no desperdiciar tiempo en la búsqueda de tales algoritmos,
centrándose, en cambio, en buscar las mejores aproximaciones que resuelvan
dichos problemas.
Como se puede apreciar,
una simple respuesta bien fundamentada del tipo “sí o no” a un problema de las
ciencias de la computación, juega un rol sumamente importante en numerosas áreas de estudio
y trabajo. El progreso de las matemáticas se vería acelerado en un mundo donde
los computadores pueden aumentar su eficiencia ilimitadamente, el área de la
seguridad y cifrado de datos sucumbiría y se tendrían que generar nuevas ideas
para proteger la información de las personas. En cambio, una respuesta negativa
frenaría la búsqueda por parte de la industria y la comunidad científica de
concretar el desarrollo de máquinas con la capacidad de resolverlo todo. No se puede negar la importancia de este problema para el mundo moderno, su solución puede cambiar radicalmente la forma en que funciona la sociedad, generando dos caminos con futuros totalmente distintos.
Bibliografía.
Cryptography. Sitio web: En.wikipedia.org.
URL: https://en.wikipedia.org/wiki/Cryptography
P versus NP, he ahí el dilema |
BBVA. Sitio web: BBVA NOTICIAS. URL: https://www.bbva.com/es/p-versus-np-he-ahi-dilema/
P versus NP problem.
Sitio web: En.wikipedia.org. URL: https://en.wikipedia.org/wiki/P_versus_NP_problem#Consequences_of_solution
P vs NP Problem | Clay
Mathematics Institute. Sitio web: Claymath.org. URL: https://www.claymath.org/millennium-problems/p-vs-np-problem
No hay comentarios:
Publicar un comentario