Tomas Bradanovic

NULLA DIES SINE LINEA. Filosofía barata, historias, historietas, mecánica, moralejas, chamullos, relatos absurdos, la vida de un vago, cosas de Arica, literatura, música, pornografía, política, física, cocina regional, minas, copete y cosas por el estilo. The awesome, absurd and often bored adventures of our Man of Mistery in Arica, from the trenches, in the Northern Front. Sacar a mil, sacar a mil. Streams of brilliance often springs from boredom. Atendido por su propio dueño, dentre nomás.

Complejidad para dummies ¿P=NP?

viernes, 13 de enero de 2017


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

9 Comments:

Blogger Ulschmidt said...

Como divulgador científico, muy bien. Esta es la explicación más potable que escuché de ese tema.

13 de enero de 2017, 09:08

 
Blogger Tomas Bradanovic said...

Solo espero que sea así jaja
Es en base a lo que he leído nomas, no alcancé a estudiar eso

13 de enero de 2017, 09:36

 
Anonymous Anónimo said...

"......es decir de fuerza bruta, aproximaciones sucesivas, etc. Ejemplo típico es la factorización de grandes números primos."

Tombrad, vuelvo con la acotacion, o redactas mal o la teoria de numeros la has reformulado.
¿factorizacion de grandes numeros primos?....si eso fuera posible ya no se estaria hablando de numeros primos, por definicion no hay ningun numero primo que pueda ser factorizado, excepto por 1....¿que matemetico intentaria factorizar un numero primo?......no querras decir "ejemplo tipico es es intento de descomponer grandes numeros en factores (primos)"....plop!!...exijo una explicacion.

Att.

INTIcondorito

13 de enero de 2017, 09:48

 
Blogger Ulschmidt said...

Ud. fue profesor adjunto de métodos numéricos !! Qué materia.
A mí me costó no poco pasarla. Todo ese asunto den encontrarle los ceros. "Newton-Raphson" me ha quedado grabado para siempre en el subconciente. Tenía un avinagrado profesor y tras varios intentos zafé con un mísero "aprobado".

13 de enero de 2017, 09:49

 
Blogger Tomas Bradanovic said...

Inti, cambia "de" por "en" y podrás dormir tranquilo. Efectivamente los primos se factorizan por 1 y por si mismos. El problema es tomar dos grandes números primos y multiplicarlos, a partir del producto debes encontrar los originales https://es.wikipedia.org/wiki/Competici%C3%B3n_de_factorizaci%C3%B3n_RSA

Ulschmidt, al menos en la época en que yo lo estudié, los métodos numéricos no eran muy complicados. Newton-Raphson (o Fourier) como todos los métodos depende mucho de la suerte al elegir el primer valor, de ahi hay que ir viendo si converge o no, estimar el error y todo eso, es un poco como jugar con el computador. Para mi era fácil porque solo tenía que implementar (programar) los algoritmos y jugar un poco, como yo tenía facilidad para programar eso me venía como anillo al dedo.

Uno de mis primeros programas era para sacar los coeficientes en las series de Fourier, pero no numérico sino programando el método analítico, era un marmotreto horrible pero creo que funcionaba, me dieron la ayudantía mayormente por eso, en esos años solo se trataba de programar los algoritmos

13 de enero de 2017, 10:10

 
Blogger Ulschmidt said...

...los métodos numéricos, aplicados a la simulación de sistemas físicos, me gustaban mucho. Me gradué o dí la materia final de la carrera con una aplicación del "modelo del Mekong" - una simulación que el cuerpo de Ingenieros de USA creo y aplicó para pronosticar el río del sudeste asiático cuando los marines andaban a los tiros con el vietcong por allá.
Pero las aplicaciones estrictamente matemáticas me resultaban mucho más áridas.

13 de enero de 2017, 19:43

 
Blogger Tomas Bradanovic said...

Claro Ulschmidt, la fuerza bruta es un gran método, pero las soluciones analíticas con un algoritmo son mucho más bonitas, no se puede negar.

13 de enero de 2017, 21:30

 
Blogger humberto jose said...

Hola envio mi posible solucion del problema P=NP para que la analicen

Sea el A {>1, < 100}2 = b2 + (2b)a + a2

Sea el B {>100, < 200}2 = b2 + (2b)a + a2 + c2 + (2c)b + 2c

Sea el C {>200, < 300}2 = b2 + (2b)a + a2 + c2 + (2c)b + (2c)2

si se programa una computadora con estas ecuaciones facilmente las puede resolver.

son mas conjuntos de numeros y sus ecuacion

saludos

28 de octubre de 2017, 17:31

 
Blogger Tomas Bradanovic said...

Humberto José, no entendí nada, francamente

28 de octubre de 2017, 17:37

 

Publicar un comentario

<< Home

Entradas antiguas Entradas nuevas