Turing:diferència entre problemes no computables i problemes intractables.

 

En su famoso artículo de 1936, del que ya se ha hablado en otras entradas de este blog, Turing hacía varias cosas notables. Primero, definía un modelo de máquina (la máquina de Turing) que permitía dar una definición matemática, y  cercana a la intuición, de qué es lo computable. Segundo, demostraba que había una "maquina universal" que podía tomar otras máquinas como datos y comportarse como ellas. Finalmente, demostraba que hay problemas (matématicos) que ninguna máquina podría resolver, que son no computables o indecidibles. Estas aportaciones se consideran muy importantes desde un punto de vista matemático y filosófico. Pero, dejando aparte la relación entre la máquina universal y los computadores actuales, ¿tienen estos resultados algún interés práctico en informática? Si consideramos que, en la última reforma de planes de estudio en Ingeniería Informática, las asignaturas que estudian estas cuestiones han pasado a ser optativas en un buen número de centros españoles, quizá la respuesta sería no. Claro que, si consideramos que estos temas son obligatorios en los estudios de informática de prácticamente todos los centros de prestigio del mundo, tendríamos que dudar de la anterior respuesta y, quizá, preguntarnos por qué algunos de nuestros centros son diferentes.

Problemas no computables

En realidad, la demostración de Turing de que hay problemas no computables lo que hace es establecer límites a la programación: señalarnos qué es lo imposible en el ámbito de las aplicaciones informáticas. Por ejemplo, el resultado original de Turing nos diría que es imposible escribir un programa que nos diga si cualquier programa dado P  terminaría su ejecución ante unos ciertos datos. Y que tampoco puede existir ningún programa que nos determine si dos programas cualesquiera hacen lo mismo. Ni si un programa, sean cuales sean los datos que recibe, siempre devuelve algún resultado.

¿Son los problemas no computables los únicos imposibles de resolver con aplicaciones informáticas? En la práctica, no. Por ejemplo, si un programa resuelve correctamente un problema, pero su coste de ejecución es inaceptable, seguramente consideraríamos que el programa es inútil. Por ejemplo, si el programa tardara varios miles de años en devolver una solución. Es decir, si las posibles soluciones a un problema tienen un coste inaceptable, entonces también consideraríamos que ese problema no puede ser resuelto. La cuestión, entonces, es si también podemos identificar esos problemas. La respuesta es sí, gracias a investigadores que se basaron en el trabajo de Turing. 

Problemas intratables

Se puede argumentar que hay problemas que no se pueden resolver ahora, pero sí dentro de unos años, con unos computadores más potentes. De la misma forma que los computadores actuales pueden ejecutar aplicaciones y resolver problemas que los de hace unos años no podían. Eso es cierto, pero hay problemas que, por muchos años que pasen, seguirán siendo imposibles de resolver en un tiempo razonable. Por ejemplo, un problema de tratamiento de textos que necesitara realizar 10ⁿ operaciones, siendo n el número de palabras del texto tratado. En particular, si el texto a tratar tuviera 20 palabras, el número de operaciones a realizar sería 10²⁰. Supongamos que, con los computadores que tenemos ahora, podemos ejecutar 300 millones de esas operaciones por segundo. Teniendo en cuenta que un año tiene algo más de 30 millones de segundos, esto quiere decir que, con estos computadores, podríamos ejecutar aproximadamente 10.000 billones de operaciones (es decir, 10¹⁶) por año. Por tanto, para resolver este problema nuestros computadores actuales necesitarían 10.000 años. Si dentro de unos años tuviéramos unos computadores 100 millones de veces más potentes, podríamos resolver el problema para un texto de 20 palabras, pues tardaríamos algo menos de una hora. Pero, si el texto tuviera 30 palabras, todavía tardaríamos un millón de años en resolver el problema. Es decir, si para resolver un problema necesitamos realizar un número exponencial de operaciones, con respecto del número o el tamaño de los datos, podemos considerar que ese problema no tiene solución informática. A estos problemas se les llama intratables y también forman parte de lo imposible en informática.

El estudio de estas cuestiones comenzó en los años 60. Se estableció que había dos tipos de coste de asociados a un programa o algoritmo: el tiempo y el espacio: cuánto tiempo tardará en ejecutarse el algoritmo y cuánta memoria será necesaria. El primer problema fue determinar cómo medir estos costes. Por ejemplo, si el tiempo lo midiéramos en términos de la cantidad de segundos que tarda ese programa en ejecutarse en un determinado computador, los resultados que obtuviéramos sólo serían válidos para ese computador. La solución, y aquí vuelve a aparecer Turing, consistió en considerar que el tiempo se debía de medir en términos del número de operaciones que necesitaría realizar una máquina de Turing para ejecutar ese algoritmo, y la memoria sería la cantidad de posiciones de cinta que utilizaría en su ejecución. Ahora bien, como el funcionamiento de un programa suele depender del volumen de datos que ha de tratar, también se consideró que las medidas de coste no debían de ser valores absolutos, sino funciones que dependen del tamaño de la entrada. Lo que puede parecer sorprendente es que esas medidas, en términos de máquinas de Turing, son válidas para los computadores reales. 

Entre los primeros resultados obtenidos en esta línea de investigación, está la definición en 1965, por Hartmanis y Stearns (premios Turing en 1993),  de una jerarquía problemas en función de su coste y de su dificultad para resolverlos. En el nivel más bajo de la jerarquía están los problemas que tienen una solución con coste constante, es decir, que hay un algoritmo que los resuelve que realiza un número fijo de operaciones, independientemente de los datos que ha de procesar. Inmediatamente por encima están los problemas con coste logarítmico, es decir, aquellos problemas para los que existe un algoritmo que los resuelve que para procesar n datos sólo necesita hacer un número de operaciones del orden de log₂(n). Por ejemplo, para procesar 8 datos, el algoritmo necesitaría ejecutar unas tres operaciones, pero, para procesar 128, sólo harían falta 7 operaciones y, para un millón de datos, bastarían unas 20 operaciones. Los problemas en estos dos niveles de la jerarquía son los que se consideran fáciles. El resto de los problemas tratables son los que están en la clase de problemas con coste polinómico. Dentro de esa clase, se encuentran las subclases de problemas lineales (que requieren un número de operaciones proporcional al tamaño de la entrada), cuadráticos (cuando las operaciones requeridas son del orden del cuadrado del tamaño de la entrada), etc. Finalmente, tendríamos los problemas intratables, es decir, los que requieren un número exponencial de operaciones.

Problemas NP-completos

Que todos los algoritmos que conocemos para resolver un cierto problema requieran un número exponencial de operaciones, no necesariamente quiere decir que el problema sea intratable. Podría ser que todavía no se nos hubiera ocurrido un algoritmo mejor. Cook (premio Turing en 1982), Levin  y Karp (premio Turing en 1985)  mostraron que la frontera entre los problemas tratables y los intratables es la clase de los problemas NP-completos, constituida por los problemas más difíciles de la clase NP, que son los que, si nos dan una posible solución al problema, podemos verificar si esa solución es correcta con un número pequeño de operaciones.  Es decir que, aunque no sepamos resolver el problema eficientemente, sí sabemos comprobar la corrección de las soluciones eficientemente. Un ejemplo típico de la clase NP (de hecho, el problema es NP-completo) es el llamado problema del viajante de comercio: Se supone que un viajante tiene que visitar un cierto número de ciudades, donde tiene clientes, para lo que tiene un presupuesto fijo. Conoce lo que le cuestan los viajes entre todas las ciudades. La cuestión es si puede encontrar un recorrido, que no exceda el presupuesto que tiene, que parta de la ciudad en que vive, termine en la misma ciudad y que visite una sola vez cada una de las ciudades requeridas. Todos los programas que resuelven este problema necesitan, en general, un número exponencial de operaciones, básicamente, porque pueden tener que considerar todas las posibles combinaciones de viajes entre ciudades. Pero si nos dan un recorrido concreto, es muy fácil y rápido verificar si éste pasa por todas las ciudades requeridas y si su coste no excede al presupuestado.

Lo que todavía no sabemos es si los problemas NP-completos son tratables o intratables. De hecho, esta cuestión se considera uno de los problemas del milenio, cuya solución recibiría una recompensa de 1 millón de dólares.

En la práctica

Muchos de los problemas no computables o intratables tienen gran importancia práctica, por lo que la imposibilidad de resolverlos informáticamente es muy mala noticia. Afortunadamente, este hecho no quiere decir que no pueda haber soluciones imperfectas. En particular, existen técnicas que permiten obtener soluciones parciales o aproximadas para problemas no computables o intratables, que pueden ser extraordinariamente útiles en la práctica.

Ferando Orejas, Lo imposible, Eñ Año de Turing, 28/02/2013

Fernando Orejas es catedrático de la Universitat Politècnica de Catalunya.