Luis Miguel Pardo recorre el zoo de la complejidad en su exposición sobre el problema “P versus NP”

Por Francisco R. Villatoro, el 5 junio, 2011. Categoría(s): Ciencia • Informática • Matemáticas • Mathematics • Mujeres en la ciencia • Noticias • Personajes • Prensa rosa • Science ✎ 5

Esta foto de Luis Miguel Pardo (Universidad de Cantabria), más serio que un guardia civil, puede engañar a muchos porque en Barcelona se nos ha desvelado como todo un “cachondo mental” en su presentación del problema “P versus NP,” la conjetura de Cook (o mejor la de Cook-Levin-Karp). Cual zoólogo taxonómico, trató de recorrer los “animales” más destacados del zoo de la complejidad (mantenido por Scott Aaronson), sin intención alguna de mostrarnos lo más interesante, la “etología” de estas clases de complejidad. Un grafo de clases que incluía a ZPP fue el leivmotiv de su charla (sí, has leído bien, ZP+PP). Luis Miguel, primero, nos trató de convencer de que el problema P vs NP está ligado de forma íntima con el problema de los ceros de Hilbert, el famoso Nullstellensatz, gracias a 3SAT (el primer problema que se supo que era NP-completo). Luego nos demostró en primera persona que el que mucho abarca poco aprieta (sus disculpas continuas porque no podía contar en tres horas todo lo que quería contar indican claramente que quizás no se preparó bien la charla). Y finalmente su interés en mostrarnos uno de los aspectos más interesantes de la teoría de la complejidad en la actualidad, la demostración de Irit Dinur del teorema PCP, quedó en eso, en su interés (no le dio tiempo a redondear su charla como al menos a mí me hubiera gustado). Aunque yo soy informático no conocía los sistemas de pruebas interactivos (que Luis Miguel nos ha ilustrado con Arturo y Merlín), ni la equivalencia IP=PSPACE (yo estudié teoría de la complejidad en 1990); esta equivalencia deja con un cierto “regusto a madera” que para redondear el “bouquet” de la charla de Luis Miguel pide a gritos más tiempo en barrica. Por lo que parece, lo único común a todos los seminarios de teoría de la complejidad por doquier es la discusión de la demostración de Irit Dinur, así que me parece que me la tendré que estudiar algún día (espero tener tiempo este verano, aunque no sé si me enteraré de algo).

La verificación interactiva de pruebas es una generalización de las técnicas de verificación de pruebas por certificados. La mayoría de los asistentes nos quedamos boquiabiertos cuando Luis Miguel nos indicó que en las pruebas interactivas entre Arturo y Merlin con k rondas, AM[k], bastaba con dos rondas AM[k]=AM[2]; de hecho, creo que muchos nos quedamos con el gustillo de enterarnos mejor de qué es lo que realmente significa esto. La clase PCP[r(n); q(n)] corresponde a los lenguajes probables con un sistema PCP que usa O(r(n)) bits aleatorios y O(q(n)) búsquedas en la prueba. Saber que NP = PCP(log(n),1) o que basta con leer 3 bits aleatorios de cada prueba para verificar han sido gratificantes sorpresas para mí. Realmente son ideas muy profundas… pero según Luis Miguel todavía estamos muy lejos de poder atacar con éxito el problema P vs NP; todos los intentos de calidad acaban introduciendo nuevas clases de complejidad entre P y NP o ligeramente por encima de NP. ¿Será posible encontrar un contraejemplo a P=NP? Según Luis Miguel dicho contraejemplo debería ser tan sutil que es mucho más difícil encontrarlo que demostrar que P y NP no coinciden por argumentos generales que no se refieran a un problema concreto.

Le pregunté a Luis Miguel una cuestión de “prensa rosa,” ¿será Irit la primera mujer en recibir una medalla Fields? Según Luis Miguel, sabiendo que ya ha sido candidata y no la ha recibido, todo depende de cómo evolucione su próximo trabajo. En su opinión, el premio “natural” para Irit es el Premio Nevanlinna (que tampoco ha recibido aún ninguna mujer). Ya veremos que pasa…



5 Comentarios

  1. “Aunque yo soy informático no conocía los sistemas de pruebas interactivos …, ni la equivalencia IP=PSPACE (yo estudié teoría de la complejidad en 1990)”

    ¿1990? Quizás no conozcas entonces y podría interesarte (creo que también eres físico) que QIP=PSPACE resultado relativamente reciente y que sorprendió a más de uno.

    Por otra parte el teorema PCP (importante por lo que dice sobre la dificultad de aproximar soluciones en problemas de optimización en NP), ya ha sido objeto de varios premios:
    –en 2001, el Godel: http://en.wikipedia.org/wiki/G%C3%B6del_Prize, a nada menos que 9 autores (salieron a 555 usd por autor).
    –en 2002 el Nevanlinna a Madhu Sudan (entre otras contribuciones).
    No sé si una prueba más sencilla merece otro premio; quizás si abre nuevas
    vias…

  2. “(sus disculpas continuas porque no podía contar en tres horas todo lo que quería contar indican claramente que quizás no se preparó bien la charla).”

    Te puedo asegurar de primera mano (soy su último alumno de doctorado) que se preparó a consciencia la charla. El problema es que pretendía contar un curso de doctorado de 20 o 30 horas en 3 y aunque es un genio (tanto dando clases como investigador) hay cosas que son imposibles.

    La verdad es que cuando me contaron este resultado lo flipé (no hay otra palabra). Es un resultado mucho más filosófico que práctico, que viene a confirmar más si cabe la importancia de la conjetura P!=NP pues “casi casi” afirma que es posible demostrar y verificar teoremas fácilmente si P=NP.

    @proaonuiq

    ¿Tienes alguna referencia el artículo donde se demuestra QIP=PSPACE?

  3. Outsider, el problema de las charlas es que cuando alguien domina un tema le es muy dificil volver a pensar mal sobre el él. Un buen pedagogo es precisamente el que puede volver a pensar mal sobre un problema.

    En cuanto al problema P versus NP se comprende fácilmente a partir de los conceptos de:
    — problema de decisión,
    –tamaño de problema,
    –algoritmo o metodo para encontrar una solución al problema de decisión,
    –método de comprobación de la solución al problema de decisión,
    — recursos usados por el algoritmo y
    — recursos utilizados por el método de comprobación.
    Todos estos conceptos se puede formalizar pero cómo esto sule añadir complejidad al asunto en lo que sigue hago una presentación muy informal:

    Un problema de decisión es basicamente un objeto matematico que admita infinitas realizaciones de diferentes tamaños (piensa en una familia infinita de objetos similares de diferentes tamaños, al que podemos llamar también el input) y una pregunta sobre ese objeto que admite una respuesta si / no. Cómo objeto matemático piensa por ejemplo en un numero entero cualquiera, un grafo cualquiera, un sistema de ecuaciones lineales cualquiera. Cómo preguntas que admiten respuestas si / no piensa por ejemplo: ¿ este número es primo si o no ? ¿este grafo se puede colorear con 3 colores si o no? Etc…Ten en cuanta que hay problemas que no son de decisión: también los hay de construcción (searching), de optimización o de conteo, aunque todos estos se pueden expresar cómo problemas de decisión, y por eso nos podemos limitamos a los problemas de decisión.

    El parámetro que expresa el tamaño del problema varia según el objeto: para numeros puede ser el numero de digitos en su expresión binaria o decimal (en general binaria), para grafos el numero de vertices n etc…

    Un algoritmo es un conjunto de instrucciones bien definidas finito que permite resolver un problema (no necesariamente de decisión) en un numero finito de pasos (no todo el mundo está de acuerdo en que un algoritmo debe terminar en un número finito de poasos). También ver nota 1 al final.

    Los recursos utilizados por el algoritmo puede ser, por ejemplo ,el tiempo (el numero de pasos u operaciones que se necesitan para que termine), el espacio (la cantidad de memoria necesaria para ejecutarlo), la cantidad bits aleatorios (en algoritmos probabilistas), la cantidad de entrelazamiento (en algoritmos cuanticos), el número de procesadores en algoritmos paralelos…

    Sobre la comprobación de la solución, imaginate que tienes el problema ¿este número es primo si o no? y alguien te afirma que lo es. Le pedirás que te lo demuestre. Para demostrarlo tendrá que utilizar recursos (del mismo tipo que los que se utilizan en el algoritmo para encontrar la solución: tiempo, espacio, bits aleatorios, entrelazado cuantico…)

    Si expresas la cantidad de un recurso utilizado en el algoritmo o en la comprobación (por ejemplo el tiempo) en función de los diferentes tamaños del problema obtienes una función, a la que podemos llamar función de complejidad computacional.

    Entonces,
    –los problemas en P tienen tanto un algoritmo que utiliza una cantidad del recurso tiempo polinómica con respecto al tamaño del problema (y por lo tanto una cantidad del recurso tiempo polinómica para la comprobación).
    –Los problemas que están en NP son aquellos que utilizan una cantidad polínómica de tiempo para la comprobación y posiblemente, hasta que se demuestre lo contrario, un algoritmo que utiliza una cantidad exponencial del recurso tiempo.
    Precisamente lo que plantea el problema P versus NP es si podemos sustituir la palabra “posiblemente” en la anterior frase por la palabra “necesariamente”. Es decir, ¿ hay problemas de decisión cuya comprobación de solución se puede realizar con una cantidad polinómica del recurso tiempo (cómo función del tamaño del problema) pero cuyo algoritmo de solución necesita necesariamente una cantidad exponencial del recurso tiempo (cómo función del tamaño del problema) ?

    Las diferentes clases del zoo se definen de manera similar, en base a diferentes recursos (no necesariamente tiempo) y de otro tipo de funciones (no necesariamente polinomicas o exponenciales).

    Una buena presentación (cómo la de Pardo lo és) de este problema para matemáticos es esta de Wigderson que hizo en el congreso de la IMU Madrid 2006: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/W06.pdf (en Inglés). Hala… a estudiar !

    Nota 1: no es necesario que lo haya diseñado Finito de Córdoba.

Deja un comentario