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

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