Nota dominical: ¿Puede un ordenador cuántico resolver el problema del viajante de forma eficiente?

Por Francisco R. Villatoro, el 19 noviembre, 2012. Categoría(s): Ciencia • Informática • Matemáticas • Science ✎ 17

El problema del viajante (TSP por Traveling Salesperson Problem) consiste en «dado cierto número de ciudades en un mapa conectadas por cierto número de carreteras, encontrar el camino más corto que un viajante de comercio debe tomar para visitar todas las ciudades exactamente una sola vez y retornar a la ciudad de origen.» Clara Grima @ClaraGrima definiría el TSP con mayor rigor como: «Dado un grafo G de vértices V conectados mediante arcos E de coste no nulo, encontrar el ciclo hamiltoniano de menor coste.» Mucha gente afirma que este problema TSP es un ejemplo de problema NP-completo, lo que es completamente falso. Un problema se puede resolver de forma eficiente si está en P. Incluso si fuera verdad que P=NP, no sabríamos si existe algún algoritmo eficiente para resolver el problema TSP. Los algoritmos cuánticos eficientes está en la clase BQP. ¿Existe algún algoritmo en BQP para el problema TSP? Nadie lo sabe, pero la opinión de los expertos es que no existe. Más aún, la opinión de los expertos es que las clases de complejidad BQP y NP-completo son disjuntas. Quizás conviene que recordemos algunas definiciones. Por cierto, todo esto viene a cuento por la entrada de Rod Hilton, «Trav­el­ing Sales­per­son: The Most Mis­un­der­stood Problem,» Absolutely No Machete Juggling, Sep­tem­ber 14, 2012, y por el comentario en este blog de josejuan.

En la teoría de la complejidad computacional se dice que un problema pertenece a la clase P si existe un algoritmo determinista para resolverlo que requiere en el peor caso un tiempo de ejecución descrito por un polinomio en el tamaño de la entrada, es decir, es O(nk), donde k≥1; un algoritmo con un coste en tiempo más que polinómico, como O(2n) no pertenece a la clase P. Se dice que un algortimo es eficiente si pertenece a la clase P, aunque de hecho, cuando k>3 un algoritmo es poco práctico.

Un problema pertenece a la clase NP si existe un algoritmo no determinista para resolverlo que requiere en el peor caso un coste en tiempo de ejecución polinómico; la «N» de «NP» significa «no determinista» aunque mucha gente se confunde con «no polinómico.» Un problema NP cumple la propiedad de se puede verificar (decidir) la corrección de una solución en tiempo polinómico. Si para verificar una solución se requiere un tiempo no polinómico, entonces el problema no pertenece a la clase NP. Por ello, el problema TSP no es un problema NP, pues decidir si una solución concreta es la óptima requiere un tiempo no polinómico.

Un problema pertenece a la clase NP-completo si es un problema NP equivalente a algún otro problema NP-completo. Esta definición recursiva exige especificar un problema concreto. Por ejemplo, el problema de la suma de subconjuntos: dado un conjunto de enteros, ¿existe algún subconjunto cuya suma sea exactamente cero? Por ejemplo, dado el conjunto { −7, −3, −2, 5, 8}, la respuesta es sí, porque el subconjunto { −3, −2, 5} suma cero. Cualquier problema NP que se pueda resolver en tiempo polinomial si existiera una solución en tiempo polinomial para el problema de la suma de subconjuntos es también un problema NP-completo (en este sentido esta clase de problemas NP es completa).

El problema TSP de «encontrar el camino óptimo» (o más corto) no es un problema NP-completo. Entres otras razones porque la clase NP-completo solo se aplica a problemas de decisión. Hay otra formulación del problema TSP, como problema de decisión que pertenece a la clase NP-completo. Clara Grima @ClaraGrima definiría el problema de decisión TSP como: «Dado un grafo G y un coste máximo k, decidir si existe un ciclo hamiltoniano cuyo coste sea menor o igual que k.» Este problema está en NP y además es NP-completo, porque el problema TSP de optimización es NP-difícil (en inglés NP-hard); aquí hay que recordar que la clase NP-completo es la intersección entre las clases NP y NP-difícil.

Un punto importante que hay que destacar es que si se pudiera resolver en tiempo polinómico el problema TSP, también sería resoluble el problema de decisión TSP (como es obvio) y con él todos los problemas de la clase NP-completo. Pero no a la inversa.

La clase BQP corresponde a los problemas de decisión que se pueden resolver en un ordenador cuántico en tiempo polinomial con una probabilidad de error acotada por 1/3, por convenio. Se trata del análogo cuántico a la clase BPP, los problemas de decisión que se pueden resolver de forma no determinista probabilística con una probabilidad de error menor de 1/3 (es decir, utilizando una máquina de Turing probabilística). Se conocen unos pocos (muy pocos) algoritmos cuánticos en BQP que se sospecha que no están en P (aunque no hay demostración de esto último), siendo el más famoso el algoritmo de factorización de enteros de Peter Shor.

¿El problema de la decisión TSP es un problema BQP? Nadie lo sabe, pero lo expertos opinan que no lo es (salvo que P=NP).



17 Comentarios

  1. Hay que tener cuidado! Hay una versión del TSP que es un problema de decisión: «dado un número X, existe un camino de coste <=X?" es una pregunta que se puede contestar por sí o no. Esta pregunta obviamente pertenece a NP! Esto es el sentido en que el TSP pertenece a NP.

    Estrictamente dicho, por definición de P y NP, estas clases contienen sólamente problemas de decisión.

    Además, incluso si se define el TSP como "encontrar el ciclo hamiltonio de menor coste", decir que "decidir si una solución concreta es la óptima requiere un tiempo no polinómico" asume que P no equivale NP…

  2. Si, como es el caso del planteo original del problema (TSP euclidiano), TSP se plantea mediante ciudades que se comunican todas entre sí y donde el objetivo es el de hallar la ruta que permita al viajero visitar una vez cada ciudad regresando finalmente a la de partida y que minimice (o maximice) una cierta función del recorrido (la distancia total recorrida es el ejemplo más simple) está claro que por «verificar la solución» no puede entenderse comprobar que la ruta obtenida representa el «minimo minimorum» (nada se opone a que varias rutas cumplan el objetivo), ya que en tal caso no podría hablarse de una comprobación en tiempo polinomial, puesto que esa verificación implica en este caso resolver de nuevo el mismo problema.

    En el caso del TSP, por comprobar una solución se suele entender el verificar meramente que la ruta visita todas las ciudades una sola vez, lo cual es claramente un trámite sencillo. Digo esto porque en el post se afirma que el TSP no es NP porque claramente no puede verificarse (en el sentido absoluto) la solución en un tiempo polinómico. Si se aplica ese criterio de modo no relajado, estoy de acuerdo, pero me sorprende que se afirme que el TSP no es un problema NP-completo, puesto que muchas veces se presenta como el paradigma de dicho tipo de problemas. En Wikipedia, por ejemplo, puede leerse

    «Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours.»

    Si bien el problema se ha resuelto para casos concretos (configuraciones particulares de nodos) con un gran número de ciudades, tengo entendido que el método general pasa por valorar todas las combinaciones posibles, con excepción de aquellas a las que se les puede aplicar el método de poda (si una nueva rama en curso arroja un valor mayor que el de un circuito ya valorado, se detiene la exploración de la misma). El número de combinaciones a estudiar es del orden de (N-1) ! (factorial), lo que hace que un computador tipo PC no pueda enfrentarse a más de una veintena de ciudades en un tiempo razonable. El carácter factorial de la exploración pone también para un supercomputador un techo de unas cuarenta ciudades. Hay que tener en cuenta que 59 ciudades representan 58! aprox = 10^78, el número estimado de átomos del universo conocido.

    Mediante algoritmos genéticos, redes neuronales, agentes (hormigas) y otros procedimientos del estilo se encuentran soluciones muy estimables, que están en el orden del 4% en torno a la solución perfecta (cuando es posible la comparación). Con estos algoritmos un PC puede trabajar con unas diez mil ciudades en tiempos del orden de la hora.

    1. Hola hicsuntdraconis , perdona la intromisión. Me ha parecido, muy interesante tu comentario al post de Francis (interesantísimo, sin duda) y me gustaría saber si tienes algunas referencias que pudieras facilitarme en relación a tu último párrafo (sobre estos métodos estadísticos para hallar soluciones al problema del viajante). Gracias.

      1. Hola, Freddy. Mediante algoritmos genéticos te puedo ayudar concretando suficientemente el procedimiento. En lo que se refiere a la solución mediante redes neuronales o agentes no programé nunca ningún modelo, pero hay bastante literatura sobre ello según creo. Ahora estoy lejos de casa, en cuanto regrese te escribo con los detalles. Hasta entonces.

  3. Esta nota tiene un error muy grave. La distinción entre las versiones de decisión y optimización de TSP son más bien técnicas, porque es mucho más cómodo trabajar con clases de problemas de decisión (o «lenguajes»). Poder resolver alguna de las versiones en tiempo polinomial implica que la otra también (es un resultado que se aprende en cualquier curso básico), al contrario de lo que escribiste:

    «Un punto importante que hay que destacar es que si se pudiera resolver en tiempo polinómico el problema TSP, también sería resoluble el problema de decisión TSP (como es obvio) y con él todos los problemas de la clase NP-completo. Pero no a la inversa.»

    El artículo en el que te basas (de nomachetejuggling.com) está escrito por un amateur que no sabe hacer búsqueda binaria.
    Lo otro que decís sobre BQP sí es correcto. Hay que destacar que la aparente arbitrariedad en la definición de BPP y BQP no es tal, porque la constante 1/3 se puede reemplazar por cualquier otra (por la cota de Chernoff).

    1. Cuidado que estos modelos no son «mágicos»: no resuelven problemas NP-completos en tiempo polinomial. Si lo fueran, estaríamos haciendo un gran esfuerzo en construir computadoras basadas en eso. Incluso tenemos la conjetura (una extensión de la tesis de Church-Turing) de que todo modelo de cómputo físicamente realizable puede ser simulado usando máquinas de Turing con slowdown polinomial.

      Estos modelos pueden dar la solución óptima en instancias chicas, pero generalmente frenan en óptimos locales (es lo que sucede con las pompas de jabón, con el plegamiento de proteínas y con estos hongos) o usan tiempo exponencial (lo que sucede con el ADN, ver http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.8878&rep=rep1&type=pdf).
      Para más información recomiendo este artículo: http://www.scottaaronson.com/papers/npcomplete.pdf

    2. Imagino que en este caso por «resolver el problema» se entiende encontrar una ruta suficientemente válida, es decir que se aprecia cercana a la óptima, pero de la que no puede afirmarse que se trate de un óptimo absoluto. Es lo que tienen en común las soluciones que no recurren a la combinatoria pura y dura. Este caso del hongo debe ser del tipo de los que se basan en el empleo de colaboración de agentes (una de las técnicas de la inteligencia artificial).

    3. Los esquemas finales resultantes en estos vídeos no responden al TSP, que exige que no quede ninguna ciudad en una rama terminal, como se aprecia aquí. Lo que ilustran estos vídeos es que se llegan a interconectar todos los nodos, lo que puede ser un objetivo deseable en alguna aplicación, pero no es lo que pide el TSP.

    4. El experimento de la red de tokio, se hizo «dandole» informacion a los hongos de la geografia de tokio y por suspuesto colocandole alimentos en las principales ciudades, y aprovechando ciertas propiedades de los hongos como su sensibilidad a la luz. es decir, se parametrizo tanto el experimento que alcanzar esa similitud no parece sorprendente.
      Respecto del experimento del protozoo, francis, ¿Es sensible el Physarum a las moleculas que libera el azucar, es decir el «olor» (que es apenas perceptible o imperceptible para el ser humano pero existe quimicamente)? Si es asi, que encuentre la solucion seria aun mas logico y menos sorprendente, que no deja de ser interesante.

Deja un comentario