P frente a NP: la pregunta abierta que sostiene la criptografía moderna
No sabemos si los problemas cuya solución es fácil de verificar son también fáciles de resolver
LA PREGUNTA EN TÉRMINOS LLANOS
Existen problemas cuya solución, una vez propuesta, es fácil de comprobar. Dado un sudoku resuelto, verificar que es correcto lleva un momento. Dada una ruta que visita todas las ciudades por debajo de cierto coste, comprobarlo es inmediato.
La pregunta es si esa facilidad de verificación implica facilidad de resolución. Formalmente: si todo problema cuya solución se verifica en tiempo polinómico puede también resolverse en tiempo polinómico.
La creencia mayoritaria entre los especialistas es que no, es decir, que resolver es genuinamente más difícil que verificar. Pero no existe demostración.
POR QUÉ IMPORTA
La criptografía de clave pública se apoya precisamente en esa asimetría. Multiplicar dos números primos grandes es trivial; factorizar el resultado es, con los algoritmos conocidos, prohibitivamente costoso.
Si se demostrara que ambas clases coinciden y la demostración fuese constructiva, con algoritmos de constantes razonables, buena parte de la seguridad informática actual quedaría comprometida.
El impacto no se limitaría a la criptografía. Numerosos problemas de optimización industrial, diseño de circuitos, planificación logística, plegamiento de proteínas y demostración automática de teoremas pertenecen a esa clase.
LA NOCIÓN DE COMPLETITUD
Un hallazgo estructural notable es que existen problemas a los que cualquier otro de la clase puede reducirse eficientemente. Se denominan completos.
La consecuencia es potente: un algoritmo eficiente para uno solo de esos problemas resolvería automáticamente todos los demás. Se han identificado miles de problemas completos en campos muy distintos, y décadas de esfuerzo no han producido un algoritmo eficiente para ninguno.
Esa ausencia es la principal evidencia empírica a favor de que las clases son distintas, aunque no constituya demostración.
POR QUÉ ES TAN DIFÍCIL DEMOSTRARLO
Se han identificado barreras formales que descartan familias enteras de técnicas de demostración. Varios resultados muestran que ciertos métodos, por su propia estructura, no pueden distinguir entre ambas posibilidades.
Esto significa que una resolución requeriría herramientas conceptualmente nuevas, no un refinamiento de las existentes.
QUÉ SIGNIFICA EN LA PRÁCTICA
Conviene una advertencia contra la lectura derrotista. Que un problema sea difícil en el peor caso no impide resolver instancias reales.
Los resolvedores modernos abordan rutinariamente problemas con millones de variables mediante heurísticas, aproximaciones y explotación de la estructura particular de cada caso. La dificultad teórica describe el comportamiento asintótico en el peor caso, no la experiencia habitual del ingeniero.
Periódico Digital · https://periodico.dreamlabstech.co/matematicas-y-computacion/articulo_001.html