16 de agosto de 2010

La importancia de P vs NP

Figura de Theory Matters Wiki.

Dado los acontecimientos de la semana que acaba de terminar, donde Vinay Deolalikar presentó un intento de prueba para el problema de P vs NP, esta entrada la escribo para poder explicar los alcances del problema mismo para las ciencias de la computación, y para todas las ciencias en general.

Cada mes se publican en ArXiv artículos que dicen resolver el problema. Algunos dicen que P=NP, otros que P≠NP, etc. La diferencia estuvo en que este artículo en particular había pasado todos los exámenes que utilizan los teóricos en complejidad para discriminar los artículos serios. Además, este estaba escrito por una persona conocida, y cuando  había enviado una versión preliminar a un grupo selecto de científicos, uno de los principales, el mismo descubridor del problema y ganador del premio Turing, Stephen Cook, había escrito en respuesta "esto parece un esfuerzo serio" (del inglés this looks like a serious effort). Esto había motivado al resto y puso a funcionar una máquina bien aceitada de colaboración científica inigualable en la red. Como lo dijo Dick Lipton, "lo que antes se hacía en meses, ahora por Internet lo hacemos en días". Para saber como terminó toda la historia recomiendo el post anterior de Alejandro donde tienen todos los enlaces. Aquí me voy a concentrar en la definición e importancia de P vs NP.

A continuación un pequeño repaso del problema. Antes que nada este es considerado el problema principal, más importante, de las ciencias de la computación. Básicamente el problema es "para ciertos problemas, lo mejor que podemos hacer es una búsqueda bruta", o como escribe Lipton "para ciertos problemas el algoritmo más obvio es el mejor". NP como sabemos quiere decir "tiempo polinomial no-determinístico", y P "tiempo polinomial determinístico". Entonces los problemas o lenguajes con algoritmos que corren en tiempo polinomial están en P, y los problemas con algoritmo en tiempo polinomial no-determinístico en NP.

Una caracterización más fácil de entender de problemas en NP es la siguiente: Sea A un algoritmo que tiene dos entradas, x que representa una instancia de un problema L (e.g. SAT, TSP, etc), y c que representa una solución al problema. Entonces L están en NP si y solo si existe un algoritmo determinístico que corre en tiempo polinomial A y existe un c tal que A(x,c)=1, i.e. que c sea una respuesta válida al problema. Generalmente a c se le llama solución, certificado, testigo o simplemente prueba, i.e. una prueba de que x tiene solución. La misma caracterización se puede hacer para P, pero esta vez el algoritmo no tiene una prueba c. Entonces decimos que L está en P si y solo si existe un algoritmo determinístico que corre en tiempo polinomial A  tal que A(x)=1.

La gran diferencia está en el certificado. Los algoritmos para lenguajes en P determinan una solución, mientras que los algoritmos para lenguajes en NP verifican una solución. Una buena analogía es: si yo resuelvo un problema matemático por mi mismo (está en P), o estoy verificando la solución de otra persona (en NP). Entonces, la diferencia radica en que estamos comparando un proceso de determinar una solución a un problema contra un proceso de verificación de una solución ya dada para un problema.

Imagen de Wikipedia.

P vs NP en términos computacionales se refiere a cotas inferiores de problemas NP-completos. La conjetura es que para estos problemas no existe un mejor algoritmo que el de fuerza bruta, i.e. P≠NP. La mayoría de los científicos creen que esto es cierto, y de ahí surgen un montón de alternativas para resolver problemas NP-completos como Búsqueda Local, Algoritmos Genéticos, etc. Y la eficiencia de estos métodos está en que pueden verificar soluciones en tiempo polinomial.

En mi humilde opinión, una prueba de que P≠NP no cambiaría mucho las cosas porque todo lo que hacemos ahora, lo hacemos en función de que P≠NP. Por ejemplo, asumimos la existencia de 1-way functions en criptografía ¿Entonces de que nos sirve una prueba de eso? Una prueba no solo nos dice si una hipótesis es falsa o verdadera, sino que al mismo tiempo ganamos mucha información acerca del problema mismo. De una prueba de P≠NP podemos descubrir muchas conexiones entre áreas de conocimiento u objetos que creíamos desconectados en nuestra teoría. Eso tiene mucho más valor que una respuesta de falso o verdadero. Esto es lo que está ocurriendo con la prueba de Deolalikar. Algunas personas nunca habían considerado conectar el finite model theory con el clustering en Random-k-SAT. El enfoque de por sí requiere más investigación y despierta mucha curiosidad.

En el aspecto filosófico, P vs NP hace la siguiente pregunta: ¿Puede la creatividad ser automatizada? Si yo escribo un libro en el que trabaje 1 año, y lo mando a un periódico para que un crítico lo lea, y la destruye completamente en 2 semanas, ¿Qué es más dificil, escribir el libro o criticar el libro? Intuitivamente el proceso creativo es más complejo y requiere más tiempo, pero hasta que no tengamos una prueba que indique sin duda alguna nunca sabremos, por la misma razón que expuse en el párrafo de arriba. Simplemente por la curiosidad del hombre, tenemos que saber (esto lo dijo David Hilbert). 

También la misma pregunta se extiende a otros ámbitos como la física. La visión de las ciencias de la computación y una parte de la comunida de físicos, es que toda nuestra realidad física es computable. Desde la evolución de los seres vivos, hasta la formación de galaxias. Todo es visto como un proceso que dado una entrada genera un salida. Entonces salen preguntas como ¿Qué tan complejo es el plegado de proteínas? ¿Qué pasa con la información y la energía en un hoyo negro que se disipa en forma de radiación de Hawking? etc, etc. Muchas de esta preguntas están siendo respondidas por técnicas de ciencias de la computación. Por ejemplo, sabemos que si P≠NP entonces no podemos viajar en el tiempo, o no podemos movernos más rápido que la luz, y otras conexiones más extrañas. Aún así, estás conexiones dan evidencia a favor de que P≠NP, o no?

Asi que P vs NP no solo se refiere a problemas que solo interesan a las ciencias de la computación. Se refiere también a problemas fundamentales de otras ciencias. Inclusive podría decirse que es una de las preguntas más fundamentales de las matemáticas. Saber si podemos encontrar pruebas eficientemente nos da conocimiento de como resolver otros problemas muy difíciles como la Hipótesis de Riemann. Es por ello que el Clay Mathematics Institute lo pone en su lista de problemas fundamentales.

Para más información recomiendo el libro Computational Complexity A Modern Approach, o el artículo de Lance Fortnow en Communications of the ACM.

7 comentarios:

  1. Vereis, hace casi 30 años un profesor me propuso un prblema de teoria de grafos, se trataba de pasar solo una vez por cada arista del grago. Ideé un algoritmo general y unas condiciones para saber si era posible un camino que él me señaló con el nombre de , euleriano. Sorprendido, me propuso otro de extrema dificultad, se trataba del camino hamiltoniano, tras semanas de esfuerzo conseguí dos algoritmos para ese enigma y las condiciones necesarias y suficientes para saber cuando un grafo es hamiltoniano. Por desgracia ese profesor era suplente y no puedo ver mis resultados que interpreté como simple curiosidad y guardé en un cajón. Ojeando esto de P contra NP, me he dado cuenta de que ese era un problema NP-COMPLETO y por tanto , de no tener errores mi trabajo, seria una prueba de la igualdad entre ambas clases. Os adelanto que, la conncepción clásiica de grafoes completamente inoperante para acoger bajo un mismo marco unificador, caminos eulerianos y hamiltonianos. Este es mi correo, por si encontrais intereante lo que os refiero: diegolopezosa@hotmail.es Un abrazo y gracias por vuestra cortesia,Diego.

    ResponderBorrar
  2. Hola Diego,

    Claro que es interesante! Lamentablemente soy un poco escéptico (algo que viene probablemente con la formación científica), pero si estás seguro de tu resultado, deberías escribirlo en claramente y lo más formalmente posible, y colgarlo en algún lugar como para que la comunidad científica te de su opinión.

    Si ya obtuviste opiniones positivas (o negativas pero para las cuales tenés una respuesta), deberías enviar tus resultados a algún congreso o revista, para que lo analicen expertos en el área y te digan si tu artículo es publicable o no (y si "no", te darán los argumentos).

    Antes de hacer todo eso, siempre es bueno asegurarse de que no hay ningún error evidente, y para eso es bueno tener la opinión de la gente más cercana: profesores de alguna universidad que conozcas, o incluso si querés mandarme un adelanto, puedo ojearlo (aunque yo no soy especialista en esta área!), supongo que Danny también se ofrecerá a mirarlo si querés.

    Saludos,
    Alejandro

    ResponderBorrar
  3. Gracias Alejandro y Danny, la verdad es que no soy experto en grafos, pero eso fue lo que precisamente facilitó un enfoque diferennte a no estar mi mente precanalizada en los conceptos clásicos. Mi miedo, segun me han advertido, viene de que al ser un problema muy goloso pueden plagiarlo, si no tengo antes garantizada la seguridad de mi paternidad sobre su posible solución. Lo tengo escrito en papel en un lenguaje con notaciones propias y que no son las oficiales, no manejo el lenguaje especializado de teoria degrafos y máxime cuando mi concepción de estos difiere tantisimo de la cásica. Quienes han ojeado mi trabajo, son matemáticos de confianza, muchísima confianza en cuanto a que no se apropiarian de mis argumentos. No están especializados en esta rama, los dos que he consultado, no encuentran, en principio, errores pero, dada la supuesta importancia del trabajo, tendria que ser supervisado por especialistas en el tema. Según uno de los que me lo miraron, dice tener una enorme semejanza con algo extraño que no entiendo llamado, MECANICA CUANTICA con caracteristicas en mis argumentos y algoritmos que equivalen a conceptos en física como la simultaneidad de estados, la decoherencia, entrelazamiento de particulas y otros que no conozco ni comprendo, Pero al parecer con un poderoso poder de cálculo. No sé que hacer Alejandro y Danny,la verdad, tengo miedo, estoy desconcertado, por que mostré el trabajo como un simple acertijo de sobremesay el primero que lo ojeo se puso pálido, me preguntó si alguien más lo habia visto y que lo guardara bajo llave.
    El trbajo enlaza algunos campos de la matemática aparentemente desconectados con los grafos, como puede ser el cálculo diferencial. En fin , no quiero aburriros con lo que, posiblemente, no fuese más que un trabajo intrascendente de un jovencito curioso. Otro abrazo y muchas gracias por vuestro tiempo Alejandro.

    ResponderBorrar
  4. Hola Diego,

    Si ya lo han visto matemáticos amigos (y de confianza), te aconsejo que les pidas a ellos ayuda para publicar el trabajo, o al menos, para enviárselo a algún especialista de su confianza.

    Dale para adelante, así avanza la ciencia, encontrando cosas nuevas, preguntándose si resolverá el problema, y, muy importante, discutiéndolo con especialistas en el tema.

    Saludos,
    Alejandro

    ResponderBorrar
  5. Cada mes aparece un paper en arXiv diciendo que resuelve el problema. Recomiendo leer el siguiente link del blog de Lance Fortnow sobre el tema. En particular el punto numero 4 de su lista.

    http://blog.computationalcomplexity.org/2009/01/so-you-think-you-settled-p-verus-np.html

    Tambien, hay que considerar que existen muchas instancias de 3SAT que se pueden resolver en tiempo polynomial. De hecho, es muy facil generar una instancia y hacer un algoritmo que lo resuelve en tiempo polinomia (por ejemplo toma una formula CNF con un numero de clausulas cercana al numero de variables). Sin embargo, la definicion de P y NP requiere de "worst time complexity". Esto es, en el peor caso, el algritmo debe de correr en tiempo polinomial.

    Para demostrar una separacion hay que demostrar una cota inferior bien fuerte (punto 4 del link de arriba). O un algoritmo en tiempo polinomial para un lenguaje NP-completo en "worst time complexity", i.e., un algoritmo quiere decir un teorema con "running-time" y correctitud probadas. En la comunidad de teoria, un algoritmo es considerado como tal cuando existe un teorema como el mencionado.

    ResponderBorrar
  6. P versus NP: es un problema el cual a mi parecer he resuelto, la situación es que algunas ideas no son ni están en el lenguaje matemático, pueden ser lo mismo pero en realidad es muy diferente, la formulación no es sencilla, me encantaría que algunos doctores o interesados en este problema me contactaran claro que estén especializados en el tema, no soy doctor, o maestro, estudio la licenciatura en economía, pero he estudiado mucho este problema y siento que esto puede ser un gran salto para la ciencia. Pero antes de publicar mis modelos necesito que personas expertas me den su punto de vista no me interesa el PREMIO solo me interesa exponerlo.
    Lesli Daldier Garcia Jarquin.

    ResponderBorrar
  7. Bueno, voy a ser taxativo y recomendarte el mismo link que puso Marcos: So You Think You Settled P verus NP

    Mis motivos?

    1) No creo que se pueda escribir una prueba de un problema matemático tan complejo sin un "lenguaje matemático". Es una prueba de matemática, y como tal o deberías poder expresarla en ese lenguaje, o no estás entendiendo el problema finalmente.

    2) No es mi área de experiencia, por eso dejo a Lance Fortnow (el autor del post en el link anterior) que sí lo es que de su punto de vista :-)

    Espero no lo tomes a mal. Creo que realmente deberías leer el post de Lance (o contactarlo si realmente no estás de acuerdo con su punto 1.)

    Saludos,
    Alejandro

    PS: Otro post a leer es este de Scott Aaronson: Eight Signs A Claimed P≠NP Proof Is Wrong

    ResponderBorrar