FERNANDO OREJAS
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 10n
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 1020. 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, 1016) 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
log2(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.
Fernando Orejas es catedrático de la Universitat Politècnica de Catalunya.
Hay 5 Comentarios
Muy interesante, lo usaremos en clase para hacer reflexionar a los estudiantes.
Publicado por: Clotet | 12/03/2013 20:21:01
Enhorabuena Fernando. Lástima que muchos de nuestros colegas sigan opinando que es más interesante que los estudiantes añadan más y más lenguajes de programación al currículo.
Publicado por: Yolanda Ortega Mallén | 07/03/2013 11:48:44
Muy interesante
Publicado por: Miguel J. Hornos | 01/03/2013 11:17:04
►►►SORPRENDENTE VIDEO revela COMO PERDER 15KG AL MES cuidando TU HIGADO. ¡¡Miralo!! http://su.pr/2we2i5
Publicado por: ►►►LAS MEJORES DIETAS REUNIDAS AQUI!!!!►►► | 28/02/2013 16:15:22
Tu país necesita tu ayuda en un nuevo juego de estrategia. Registrate en gratis en [ http://bit.ly/123Estra ] desde tu navegador.
Publicado por: Cardios | 28/02/2013 8:45:17