P versus NP. ¿Nunca lo entendiste?

Diagrama de clases de complejidad La cuestión de la inclusión estricta entre las clases de complejidad P y NP es uno de los problemas abiertos más importantes de las matemáticas. El Instituto Clay de Matemáticas (Cambridge, Massachusetts) premia con un millón de dólares a quién sea capaz de lograr la resolución de esta conjetura. Alguien en una ocasión me explicó éste problema con un ejemplo muy sencillo de entender. Me apostaría lo que fuese a que la mayoría de los lectores de aquí no sabrían resolver manualmente una raíz cuadrada, aunque no me cabe ninguna duda a que todos sabrían elevar un determinado número al cuadrado. Llegamos a la conclusión que resolver una raíz cuadrada (que existe un método muy laborioso) es más complicado o lento que la operación inversa.

Si un problema nos pide que comprobemos si un número determinado X es la raíz cuadrada de Z podríamos resolverlo de dos formas:

Calculando la raíz de Z y comparando con X (proceso lento y engorroso)
O bien, elevando al cuadrado a X y comparando con Z (simple multiplicación X·X)

La conclusión que sacamos de éste sencillo ejemplo es que en algunos problemas comprobar la solución es más eficiente que calcularla. La complejidad de la función “elevar al cuadrado” es más simple que calcular la raíz cuadrada. ¿Qué tiene que ver todo esto con P=NP? Pues bien, P es la clase de complejidad que contiene problemas de decisión que se pueden resolver en un tiempo polinómico. P contiene a la mayoría de problemas naturales, algoritmos de programación lineal, funciones simples,... Por ejemplo la suma de dos números naturales se resuelven en tiempo polinómico (para ser más exactos es de orden 2n). Entre los problemas que se pueden resolver en tiempo polinómico nos encontramos con diversas variedades como ~~los logarítmicos (log(n)),~~ los lineales (n), los cuadráticos (n2), los cúbicos (n3),... Volviendo al ejemplo principal llegamos a la conclusión que la función de elevar al cuadrado está contenida en la clase P.

La clase de complejidad NP contiene problemas que no pueden resolverse en un tiempo polinómico. Cuando se dice que un algoritmo no puede obtener una solución a un problema en tiempo polinómico siempre se intenta buscar otro procedimiento que lo consiga mejorar. Frente a los problemas contenidos en P tienen métodos de resolución menos eficaces. Podemos ver que la operación de calcular la raíz cuadrada se encuentra contenida en esta clase.

Si nos resulta sencillo encontrar una solución para un determinado problema, sabemos comprobar si la solución es cierta (simplemente comparar), por lo que P es un subconjunto de la clase NP. La gran cuestión es si ocurre lo mismo a la inversa, es decir, si tengo un problema que sé comprobar fácilmente si un resultado es una solución, ¿sé calcular una solución sencillamente? ¿Todo problema se puede resolver en tiempo polinómico? Si alguien conoce la respuesta que se dirija al Instituto Clay y recoja su millón de dólares.

Más información | P versus NP en Wikipedia (Inglés)

Más noticias sobre: Matemáticas, Computabilidad
Comentarios (9) | Trackback

Comentarios

P versus NP. ¿Nunca lo entendiste?

La cuestión de la inclusión estricta entre las clases de complejidad P y NP es uno de los problemas abiertos más importantes de las matemáticas. El Instituto Clay de Matemáticas (Cambridge, Massachusetts) premia con un millón de dólares a quién...

#1 | Escrito por meneame.net | 27 ago 2006 16:24:21

Me recuerda a Teoría de Algoritmos... Felicidades por el primer post ;)

#2 | Escrito por DraXus | 27 ago 2006 16:55:40

Lo primero es felicitaros por el blog q sigo todos los dias, por lo general suele tener artículos muy interesantes y bien explicados, pero en este caso has metido la pata en varias puntos, me explico:

El ejemplo me parece fantástico, pero NO es verdad que calcular una raíz cuadrada este en NP, de hecho NO TENEMOS NI GUARRA DE COMO CALCULARLA (es un problema INDECIDIBLE) Te pongo un ejemplo, cual es la raiz de 2?¿?¿? Es un número irracional de infinitas cifras decimales NO periódicas (esto lo sabían ya los griegos y es posiblemente la demostración matemática más sorprendente) así que si te digo que me la calcules NO PODRÁS JAMÁS escribirla. Pero es que es aun peor, si yo te digo que cierto número es la solución al problema (dándote un algoritmo) JAMÁS podrás decidir si es verdad o mentira (salvo teniendo una demostración detrás), porque simplemente no podrías para de comprobar cifras (es un problema reducible al "problema de parada" que seguro todos los informáticos conocen).

Existen algorítmos que te dan la raíz de un número con tantas cifras como tu quieras, pero jamás la calcularán. Esto desde el punto de vista "numérico" desde el punto de visto algebraico se hace un "rodeo" y se utilizan "extensiones algebraicas", vamos hablando a groso modo, es una especie de chapuza. ¿Qué no podemos escribir raíz de 2?, pos nada le damos un símbolo nuevo y a tirar pa'alante. Así con todos las soluciones a polinomios que se te pueden ocurrir. Al conjunto que se forma se le llaman los "números algebraicos" y están contenidos en C, ojo que i el número imaginario es raíz de x^2 + 1 = 0. R tiene unos cuantos, bastantes, números más.

Bueno que me disperso. Aclarado el tema de la raíz empezamos con las clases de complejidad propiamente dichas.

Para empezar log(n) no es una clase polinomial, es todo caso es MEJOR que polinomial y formaría una clase distinta. De hecho la primera vez que la veo definida es una charla que se va a impartir en el ICM2006 en Madrid el martes 30 a las 17 horas (a la que pienso acudir porque es revolucionaria) De hecho, la existencia de un algoritmo en la clase log(n) significaría que SIN NECESIDAD de haber leído TODA la entrada SEA CAPAZ SIEMPRE (con alta probabilidad) dar una respuesta. A mi personalmente me parece increíble.

Ahora pasamos a las clases. Existe infinitas clases de complejidad. La primera, como bien dices, es la clase P de los problemas que se pueden resolver en tiempo polinomial (y pones varios ejemplos) Ahora bien, la clase NP no es EL RESTO DE LOS PROBLEMAS. Esta es una definición MUUUUUUUUUY MALA que la suelen dar los que no tienen ni idea del asunto. Ahora bien, explicar lo que es la clase NP es un tema un tanto escabroso simplemente porque se basa en un concepto de computación ABSTRACTO Y NO REALISTA. Voy a intentar explicarlo:

Los ordenadores actuales son deterministas, si tu le das el mismo input ellos te devuelve el mismo output (salvo en los casos de algoritmos probabilísticos en los que hay un input que se escoge al azar, pero si en vez de dar el input al azar se escogiera a mano, el algoritmo se comportaría igual que antes... sólo que puede que no funcione) Bueno y ¿a qué viene todo esto? Pos fácil, que pasaría si tubiéramos ordenadores capaces de dar más de un output a la vez? En realidad no es tanto dar el output, sino de tomar MUCHOS caminos a la vez para llegar a la solución. El ejemplo más fácil que se me ocurre es el de recorrer una ciudad. Si tu pudieras ir recorriendo TODAS las calles que se encuentran en un cruce A LA VEZ irías mucho más rápido, ¿no? Pues algo así es lo que sucede con estos "ordenadores".

La clase de complegidad NP sería la de los problemas que se pueden resolver en tiempo polinomial con uno de estos ordenadores. ¿Ejemplos de problemas en esta clase? Pues los más famosos son: "El problema de la mochila", "Hallar el camino hamiltoniano (¿o es el euleriano?) de un grafo", incluso "el tetris" creo que es un problema NP completo ;) Otro de los problemas NP completos famosos es el de factorizar un número es una multiplicación de números primos. Esta es la base sobre la que se sustenta el RSA, posiblemente el método de encriptación de mensanes de clave pública más usado en la actualidad. Luego hay una rista de problemas filosóficos como el de "¿Qué es más fácil, aprovar con chuleta o sin ella?" "¿Qué es más fácil, hacer la demostración de un teorema o simplemente seguirla?"

Ahora, la gracia del asunto está en que: ¿podemos emular con un ordenador actual uno de estos ordenadores no derminísticos sin ir MUUUUUUUUUUUUUUCHO más lento?. El que tenga la respuesta, se lleva un millón de dolares, donde respuesta se acepta cualquier cosa, como: No, Si o más puta, NO LO PODREMOS SABER NUNCA (esta es mi preferida ;) )

Existe INFINITAS clases de compegidad y cada día definen alguna nueva. Lo mejor es mirarse la wikipedia que tiene un buen resumen de ellas (la he usado para un trabajo fin de carrera y esta citada en él)

Sobre este tema hay miles de cosas muy interesantes que contar ;) solo hay que wikipear un poco ;)

PD: perdón por el tocho, pero creo que vale la pena ;)

#3 | cruzki | 27 ago 2006 20:43:48

Muy buenas cruzki. Le animo a aportar y a sugerir cuando lo vea conveniente :) Le voy a contestar los 2 puntos que comenta:

"Para empezar log(n) no es una clase polinomial, es todo caso es MEJOR que polinomial y formaría una clase distinta."

Por supuestísimo que no es una clase polinomial. Ida de olla total. Gracias por el reporte.

"Ahora bien, la clase NP no es EL RESTO DE LOS PROBLEMAS. Esta es una definición MUUUUUUUUUY MALA que la suelen dar los que no tienen ni idea del asunto."

También estoy de acuerdo con usted, pero es que no he comentado en ningún lugar que NP el conjunto complementario de P, es decir, todo lo que no esté en P está en NP.

Gracias por expandir la información referente al artículo. Un cordial saludo :)

#4 | Escrito por Alfonso Jiménez | 27 ago 2006 21:27:53

Es cierto, lo lei mal. Mis disculpas. Es que no es la primera vez que lo veo y de hecho es muy feo verlo / oírlo / leerlo en algún artículo que ya cansa...

#5 | cruzki | 28 ago 2006 00:26:42

Solo selañarte que no tienes ni idea, como tantos... NP no significa no polinomico, sino tiempo polinomico en máquinas no deterministas.. la proxima vez que intentes enseñar algo, procura saber algo del tema.

#6 | critico | 28 ago 2006 01:07:39

Bueno entonces qué. ¿Este señor está equivocado o sois vosotros?
Por favor, creo que deberíais de ejemplificar lo que afirmais porque con decir "eso está mal" no ayudais a nadie.
Saludos.

#7 | Quark | 28 ago 2006 16:52:41

Quark fíate de cruzki. El post está bien con las correcciones de cruzki. Lo que dice el faltón del crítico son ganas de insultar. Es cierto que NP no es "no polinómico" pero en el post no se dice eso. Se dice que NP contiene problemas que no se pueden resolver en tiempo polinómico. Seguro q crítico sabe muy bien la diferencia entre suficiente y necesario; así que sobraba su respuesta (aunq es importante saber que NP es polinómico en máquinas no deterministas)

#8 | tor | 28 ago 2006 18:17:53

Solo una apreciacion sobre la aportacion original. En la linea :

"La clase de complejidad NP contiene problemas que no pueden resolverse en un tiempo polinómico..."

Primer punto. Computacionalmente resolver lleva implicito el concepto de tiempo polinomial por lo tanto resolverse en tiempo polinomico es un pleonasmo.

Segundo punto, es un hecho que nadie sabe como resolver estos problemas, pero eso es diferente de decir de forma determinante que no se pueden resolver.

#9 | Luigi | 29 ago 2006 18:41:17

¡Añade tu comentario!