P versus NP. ¿Nunca lo entendiste?

Alfonso Jiménez 26 de agosto de 2006 8 comentarios

Diagrama de clases de complejidadLa 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

  • 1 Avatar
    DraXus | 1 estrellas
    ↓

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

    27 ago 2006 16:55 Permlink
    normal
  • 2 Avatar
    cruzki | 1 estrellas
    ↓

    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

    27 ago 2006 20:43 Permlink
    normal
  • 3 Avatar
    Alfonso Jiménez | 1 estrellas
    ↓

    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 :)

    27 ago 2006 21:27 Permlink
    normal
  • 4 Avatar
    cruzki | 1 estrellas
    ↓

    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...

    28 ago 2006 00:26 Permlink
    normal
  • 5 Avatar
    critico | 1 estrellas
    ↓

    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.

    28 ago 2006 01:07 Permlink
    normal
  • 6 Avatar
    Quark | 1 estrellas
    ↓

    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.

    28 ago 2006 16:52 Permlink
    normal
  • 7 Avatar
    tor | 1 estrellas
    ↓

    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)

    28 ago 2006 18:17 Permlink
    normal
  • 8 Avatar
    Luigi | 1 estrellas
    ↓

    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.

    29 ago 2006 18:41 Permlink
    normal

Destacado

Suscríbete