El estado actual del problema P distinto de NP

Por Francisco R. Villatoro, el 5 septiembre, 2009. Categoría(s): Ciencia • Computación cuántica • Informática • Science ✎ 6

Dibujo20090905_p_versus_np_in_the_simpsons_tv_series

El estado actual del problema P versus NP se resume en que el problema sigue abierto. Aunque se han hecho grandes avances, no se atisba que una demostración vaya a ser obtenida en las próximas décadas. ¿Pueden los computadores cuánticos resolver los problemas NP completos en tiempo polinomial? Nadie lo sabe, pero la respuesta oficial es que parece que no pueden. El millón de dólares para quien demuestre que P≠NP seguirá generando intereses. ¿Qué pasaría si alguien demuestra que P=NP? Según los estatutos del Premio del Milenio, no recibirá ni un solo dólar, aunque sí fama mundial. Bueno, en serio, recibiría 5 millones de dólares ya que podría resolver el resto de los 7 problemas del Milenio en un tiempo razonable con un demostrador automático si las correspondientes demostraciones tienen, digamos, 100 páginas de longitud. Nos lo cuenta Lance Fortnow, «Review article. The Status of the P Versus NP Problem,» Communications of the ACM 52: 78-86, 2009 [versión gratis html]. Un resumen breve en la presentación PowerPoint de la reciente charla de Scott Aaronson del MIT en «Has There Been Progress on the P vs. NP Question?» (visto en su blog «Barriers to snarky blogging,» Shtetl-Optimized, August 27th, 2009).

¿Qué es el problema P versus NP? Un algoritmo para resolver un problema es eficiente si su coste en tiempo es un polinomio dado en el tamaño de los datos de entrada. La clase de problemas para los que existen algoritmos que los resuelven de forma eficiente se denomina clase P (problemas resolubles en tiempo polinómico). Hay problemas para los que una posible solución se puede verificar en tiempo polinomial (hay un algoritmo en P que decide la validez de una solución). Este tipo de problemas se encuentran en la clase NP (problemas resolubles de forma no determinista en tiempo polinómico). El problema P versus NP trata de estudiar si es cierto o no que P=NP, es decir, que todo problema para el que se puede verificar eficientemente su solución es un problema para el que se puede calcular su solución de forma eficiente.

La clase de problemas NP completos (NP-c) es una clase de problemas que son equivalentes entre sí de tal manera que si alguien encuentra un algoritmo eficiente para uno de ellos, automáticamente obtiene una algoritmo eficiente para todos los demás problemas en NP-c, más aún, también lo será para todos los problemas en NP. Es decir, un algoritmo eficiente para un problema NP-c automáticamente implica que P=NP. Hoy en día se conocen cientos de problemas NP-c (y cientos de demostraciones falsas («fake«) de que se encuentran en P).

La mayoría de los investigadores en informática teórica cree que P≠NP, pero desde 1972 múltiples intentos de demostrar esta conjetura han sido infructuosos. En el año 2000, uno de los problemas del milenio del Instituto Clay de Matemáticas donará un millón de dólares a quien demuestre que P≠NP, aunque ni un solo dólar a quien demuestre que P=NP. En un mundo donde P=NP muchos estarían contentos, habría algoritmos eficientes («rápidos») para muchos problemas, sin embargo, muchos otros estarían tristes, la criptografía (cifrado) de clave pública sería inútil (habría algoritmos que desvelarían las claves secretas «rápidamente»). La mayoría de los expertos en teoría de la complejidad creen que P≠NP y que su demostración sólo es cuestión de tiempo.

¿Cómo se puede demostrar que P≠NP? Se han estudiado muchísimos caminos prometedores en los que se ha llegado a un callejón sin salida. Se ha avanzado mucho, pero todavía no se ve la luz al final del camino. Por ejemplo, si alguien encontrara un algoritmo en NP capaz de simular todos los problemas en P, entonces se podría utilizar un argumento de diagonalización (similar al usado por Turing para el Problema de la Parada) para demostrar que P≠NP. Los avances más importantes en los últimos años vienen en la línea que utiliza la geometría algebraica y la computación con números reales. Más detalles en el artículo de Fortnow, que se lee fácil para cualquier informático.

¿Pueden los ordenadores cuánticos resolver problemas NP completos? Peter Shor demostró que el problema de factorizar números enteros en factores primos y el problema de calcular logaritmos discretos se pueden resolver en tiempo polinómico con un algoritmo cuántico. Sin embargo, nadie sabe si estos problemas se encuentran en NP-c. De hecho, los expertos creen que el trabajo de Shor apunta a una demostración de que no lo están. Más aún, los trabajos de Grover parecen indicar que los algoritmos cuánticos (salvo excepciones como el algoritmo de Shor) sólo pueden lograr un speed-up cuadrático.

Para acabar, ¿en qué se ha avanzado en el problema P versus NP las últimas décadas? Básicamente se han obtenido resultados particulares (algunos con demostraciones muy complicadas), que según los expertos deberán estar incluidos en cualquier demostración del resultado general. Estos resultados permiten saber rápidamente si cualquier nueva «demostración» es correcta o no sólo echándole un vistazo. Si no incluye estos resultados particulares, debe ser incorrecta y los expertos «pasan» de prestarle más atención. Según Scott Aaranson es como el problema de la gravedad cuántica, cualquier propuesta debe demostrar que incluye la mecánica cuántica y la gravedad de Einstein, si no lo hace, nadie creerá que es la respuesta correcta.



6 Comentarios

    1. Gracias, Alfonso FR, muy interesante y refrescante la lectura.

      Con las demostraciones de los grandes teoremas pasa muchas veces, mucha gente se acerca al borde del precipicio, salta y alcanza el otro borde del precipicio con un pie, pero en matemáticas no basta con poner un pie en el otro lado, ni con poner los dos pies, hay que lograr mantener el equilibrio y no caer al vacío. Muchos acaban cayendo al vacío antes de que un genio muestra que saltando en el lugar adecuado, cualquiera puede saltar con éxito.

  1. CARTA ENVIADA A:
    CLAY MATHEMATICS INSTITUTE
    One Bow Street
    Cambridge, Massachusetts 02138
    USA
    Main: (617) 995-2600
    Fax: (617) 995-2660
    Email: general@claymath.org

    To whom it may concern:

    P vs NP Problem

    “Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker’s list also appears on the list from the Dean’s office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.”

    SOLUTIONS TO THE PROBLEM: P VS NP

    Regarding the problem with my conclusions are:

    1. If the number of results exceeds the number of atoms in the calculation device, or even the same universe, it is virtually impossible to obtain complete those results. And that it is not a programming problem. Therefore, storage of this number of results is so great that there is no electronic or not electronic device that may contain this very high number of results, and on the other hand, no man or group of human beings would be able to evaluate these numbers so huge. That is obviously impossible and of course no reasonable.

    2. Example: A googol is greater than the number of elementary particles in the known universe, which are estimated to be between 1079 and 1085. Looking at it another way, a googol is so great that to print a number of points equal to a googol in which each occupies 0.35 mm, need a paper 3.5 x 1096 m. wide. The diameter of the known universe is 7.4 × 1026 m, that is to say, the distance we need to print a googol of points is 4.7 × 1069 times larger than the universe. ¡And the possible results of the above problem: P vs NP are even larger; about 1247 × 10245!

    3. Obtaining or not a certain type of results (in full) to some kind of problems is determined by the size of the device.

    4. All the problems P (easy to find) can be NP (easy to check), and all NP problems (easy to check) can be problems P (easy to find) depending on the kind, nature, structure, computing capacity and (some times) size of the calculating device and not only of the programming or algorithm of the calculating device. For example, if you only have the fingers of your hand and pretend to settle accounts with numbers above 100 units, that will be a problem in many ways.

    5. Often is possible to obtain partial results of this kind of problems (P) in electronic devices; it depends on a suitable program (algorithm) of the calculating device.

    6. On the other hand, the decimal system itself, by its nature, presents problems for obtaining certain results more efficiently. In some cases, a different system work better than other, such as the hexadecimal system used in computers, for example, the case of different computer languages, some are more suitable than others for different data processing: graphics, mathematics, drawing, etc.. If you count with your fingers (10), the decimal system is most appropriate, if you count with the phalanges of your fingers (12, counting with the thumb), the duodecimal system would be most appropriate. In the present case, even with a different numbering system is not possible to obtain the complete results as already indicated above.

    I’ve attached a small program in Excel which displays partial results to the problem of organizing housing accommodations for 400 students and with a list of 25 pairs of incompatible students which I think that solves the problem in human terms. Of course other programs can be better than mine because I’m not a skilled programmer, but mine is only one example of the possible solutions.

    Kind regards.

    JOSÉ GERARDO CHAVEZ ROSAS.
    DIR.: CARRILLO PUERTO # 173-C 501
    COL. POPOTLA, DEL. MIGUEL HIDALGO
    CIUDAD DE MÉXICO, D.F. MEXICO
    TEL.: +52 55 28 73 06 85
    MAIL: gerardochav@yahoo.com.mx

  2. Hola, muy interesante el articulo yo creo que dan 1 millon de dolares a quien demuestre que P!=NP porque ellos creen que asi sea, y asi la gente, «para ellos», no pierde el tiempo intentando demostrar lo contrario. Lo que si yo creo que si lo de cuantica se da, no importa si son distintos o no, el demostrador matematico tambien vendria. Mi opinion muy particular P=NP

  3. No entiendo como con un argumento de diagonalizacion y un algoritmo capaz de solucionar np en p.
    ¿que tiene que ver el argumento de diagonalizacion y el algoritmo?

Deja un comentario