Complejidad para dummies ¿P=NP?

Entremés: universidad para todos (especialmente para los incapaces)
Veo en la tele con gran tristeza como las matriculas a primer año de las universidades alcanzan niveles record, Nunca antes había sido tan fácil ¡y gratis! estudiar en la universidad. Pobres tontos, no se imaginan el brutal engaño en que están cayendo, sus títulos -si es que lo obtienen no van a valer nada. Perderán años de vida en un simulacro de educación superior, que no es otra cosa que un muy lucrativo negocio, especialmente para directivos y profesores de las universidades estatales. Al lado de esta estafa, la Madame Mim, de los quesitos, es una simple aficionada. En fin, vamos a algo más agradable.

Un poco más de matemáticas P = NP
En la entrada de anteayer mencioné que entre los problemas matemáticos no resueltos, P=NP es fundamental, de enorme importancia en las matemáticas aplicadas: voy a tratar de explicarlo de manera informal e intuitiva porque de manera formal no me da la neurona para entenderlo. Veamos antes un poco de historia.

Machacando números
Junto con la aparición de los computadores, aparecieron las soluciones matemáticas por "aproximaciones sucesivas" que permitían resolver problemas que no tienen solución analítica, es decir sin un método o algoritmo bien definido. Esos problemas se pueden atacar usando la capacidad de los computadores para hacer millones de aproximaciones sucesivas, poniendo unos valores iniciales que se van cambiando a medida que muestran resultados prometedores. Finalmente el resultado "converge" hacia un cierto valor que sería la solución.

Así se resuelven por ejemplo ecuaciones diferenciales que no tienen solución analítica y otros problemas por el estilo. Ese campo se llama "métodos numéricos" y cuando yo estudiaba fui ayudante de ese curso, en los 80 era una rama que recién aparecía. El método es análogo a la selección natural de las especies en biología.

Fuerza bruta
En principio cualquier problema matemático se podría resolver con estos métodos numéricos o de fuerza bruta. Hay muchos problemas reales, simples de formular pero extremadamente difíciles de resolver, por ejemplo este:

Si queremos determinar todas las formas posibles de asignar 70 personas a 70 trabajos diferentes de forma que todas las personas tengan un trabajo y ninguna plaza quede vacante, no sería difícil (para quien posea cierta base matemática) establecer la solución: 70! (setenta factorial). Sin embargo, el cálculo de este número sería equivalente a un número del orden de 10 elevado a la centésima potencia, lo que significa que ni en la edad del universo podría resolverse computacionalmente este problema.

Tiempo polinómico
El problema es que cuando se requieren tantos intentos, resulta imposible de resolver en la práctica, por eso se inventó el concepto de "tiempo polinómico" que dice que si un problema tiene n variables, puede ser resuelto si el número de intentos requeridos se puede expresar en un polinomio, es decir en la forma:

P1n^exp1+P2n^exp2+P3n^exp3....  por ejemplo 5n^4+6n^15-12n^3

Lo que caracteriza a un polinomio es que n está siempre en la base, no es una potencia, por ejemplo
12^n+6^n-1 no es un polinomio, porque están elevados a una potencia de n, estos últimos se llaman tiempo exponencial. ¿Y como se sabe n? Si no me equivoco se determina por análisis combinatorio, n serían todas las combinaciones posibles para llegar al reultado. Espero no haberme equivocado, de ser así que un matemático me corrija.

La cosa es que si un problema se puede resolver en tiempo polinómico, entonces -al menos en teoría- se puede solucionar con computadoras, es decir no tomará la edad del universo ni nada parecido, Tal vez ya se han dado cuenta que existen a lo menos tres clases de problemas según su complejidad:

1.- Los de complejidad P, son los que pueden ser resueltos en tiempo polinómico en una Máquina de Touring determinista, no se asusten, en castellano esto simplemente significa "los problemas a los que les conocemos la receta, el algoritmo, para solucionarlos", por ejemplo las cuatro operaciones aritméticas, etc. (algoritmo = receta, procedimiento conocido)

2.- Los de complejidad NP, son los que podrían ser resueltos en tiempo polinómico con un método no determinista, es decir de fuerza bruta, aproximaciones sucesivas, etc. Ejemplo típico es la factorización de grandes números primos.

3.-Los malditos problemas que no pueden ser resueltos por ninguna forma factible conocida, o sea que no tienen algoritmo conocido, no pueden resolverse en tiempo polinómico o ambas.

Si definimos a P y NP como conjuntos, es decir dos universos de problemas, es intuitivo -y puede demostrarse- que P está incluído en NP, o sea todos los problemas que tienen un algoritmo y se pueden resolver en tiempo polinómico, también pueden resolverse en tiempo polinómico por fuerza bruta.

La gran incógnita es si NP está incluido completamente en P, o sea si son iguales. Esto querría decir que para todos los problemas que se pueden resolver en tiempo polinómico existe un algoritmo.

Hablando informalmente podemos decir que los problemas de complejidad P son "fáciles" es decir tienen una receta conocida. Los problemas NP en cambio son los que no les conocemos receta y estamos obligados a atacarlos con fuerza bruta.

La cuestión si P=NP entonces se puede explicar -intuitivamente- de la siguiente manera: "Si P es igual a NP entonces -en principio- cualquier problema matemático tiene un algoritmo, una receta que permite resolverlo de manera eficiente. Si P es distinto de NP entonces existen problemas matemáticos que no tienen algoritmo". Al decir "no tienen" se refiere a que puede demostrarse teóricamente que ciertos problemas no pueden tener un algoritmo, no es que no se conozca sino que no pueden y dependen enteramente del tiempo que toman por fuerza bruta.

Esto tiene enorme importancia práctica. Por ejemplo el problema de factorización de grandes números primos es la base de casi todos los métodos de encriptación con clave pública, en los años 80 se usaban números primos de 256 bits pensando que ningún computador los podría factorizar en tiempo polinómico, Con el´aumento acelerado del poder de cálculo, se empezaron a romper estas claves obligando a usar números primos más y más grandes, hoy creo que se usa encriptación de 1024 bits, según leo en Wikipedia:

Si n tiene 512 bits o menos, puede ser factorizado por varios cientos de computadoras como en 1999. Un dispositivo hardware teórico llamado TWIRL descrito por Shamir y Tromer en el 2003 cuestionó a la seguridad de claves de 1024 bits. Se recomienda actualmente que n sea como mínimo de 2048 bits de longitud.

El peligro en este caso no es tanto el avance del poder computacional, que va haciendo vulnerables a las encriptaciones antiguas, el real peligro sería que alguien encuentre un algoritmo para resolver el problema rápidamente sin importar el largo de la clave, eso quebraría completamente toda la seguridad de encriptación de los métodos basados en el RSA, sería un verdadero terremoto. Y si P=NP entonces ese algoritmo tendría que existir, sería solo cuestión de encontrarlo.

Así al menos es como yo lo entiendo intuitivamente, mi idea podría ser equivocada o incompleta, si alguien tiene otra mejor, adelante. Lo que yo creo que se ignora en el fondo es hasta donde se pueden usar algoritmos para resolver problemas, es decir si existe algún límite teórico de modo tal que alguna clase de problemas simplemente no pueden ser resueltos por ninguna clase de algoritmos. Faltaría alguien haga un aporte a la Teoría de la Complejidad Computacional análogo al que hizo CLaude Shannon a la Teoría de la Información.

P.D. Como dijo Ché Copete "si la cago me avisan". Cualquier precisión, corrección, desmentido o lo que sea, bienvenido