De lo fácil a lo imposible (segunda parte)

En la primera parte de esta aportación http://sudcalifornios.com/item/de-lo-facil-a-lo-imposible-primera-parte  , comentábamos sobre la manera como los expertos en computación clasifican los problemas, desde los fáciles a los imposibles, pasando por toda clase de difíciles. Como se mencionó, esta es la dificultad computacional, es decir, qué tan costoso es llegar a la solución de un problema siguiendo un algoritmo. Tal costo se paga o con tiempo de cómputo medido en pasos de un algoritmo o con espacio requerido para guardar cálculos intermedios. Se dice que entre más costoso es más difícil. Distingamos ahora tres conceptos básicos: algoritmo, problema e instancia.

Algoritmo es una sucesión determinada de pasos para lograr un objetivo. Un problema es algo que se desea resolver y para llegar a la solución suele haber varios algoritmos. Así, el problema de ordenar alfabéticaente una lista con nombres es un problema que puede resolverse de muchas maneras, algunas más eficientes que otras. Una instancia (de un problema) es un caso particular fijo, por decir, ordenar la lista de nombres (Caro, Miguel, Alma, Beto, Paco) es un problema de ordenamiento fijo.

Por lo general, al referirnos a un problema no nos referimos a ninguna de sus instancias en particular, sino a todas ellas en conjunto. Obsérvese que para una instancia fija puede haber un algoritmo especial que no sirva para otras instancias, por lo que ese algoritmo no resuelve el problema de ordenamiento, sino sólo la instancia de referencia. Por ejemplo, para ordenar los números (1,2,4,3) basta invertir los últimos dos como único paso, pero no sirve para (la instancia) (1,3,2,4).

En la primera parte, se mencionaron 3 problemas: búsqueda, ordenamiento y agente viajero. Los primeros dos son problemas considerados fáciles, mientras que el último se considera difícil. Ese camino no termina ahí. Hay clases de complejidad que agrupan problemas más difíciles, muy difíciles, superdifíciles y se puede llegar hasta los problemas imposibles. Veamos algunos de estos casos.

Todo juego de estrategia entre dos jugadores es por lo general un problema muy dificil, requiriendo muhco tiempo y mucho espacio para ser resueltos de manera óptima. Es el caso de las damos o el ajedrez. Determinar si dos fórmulas matemáticas son equivalentes es un problema aún más difícil.

Resulta interesante que hay problemas que aún no se sabe qué tan difíciles son. Por ejemplo la factorización de enteros. Dado un número entero, descomponerlo en sus factores primos. Por ejemplo:

897  = 3x13x23

168993 = 3x3x11x569

Este problema es de gran importancia práctica pues de eso depende de la seguridad de la mayoría de las comunicaciones entre computadoras, lo que no es poco decir. Resulta que los dos ejemplos anteriores son relativamente fáciles, pero para proteger computadoras se emplean números de cientos de cifras cuya factorización es realmente tardada por los métodos conocidos. Aunque hay algoritmos eficientes para descomponer en factores primos, se desconoce si hay un algoritmo óptimo para hacerlo. Se presume que el problema es tan dificil como el del agente viajero pero nadie lo ha podido demostrar.

Casi toda persona que trabaja con computadoras, tablets o celulares, ha tenido la experiencia de sentir que el dispositivo que está utilizando se quedó trabado, como cotidianamente se dice. Al punto de que le quitamos la pila al celular o reiniciamos la computadora pues no tenemos idea si se recuperará solo y ya ha sido demasiada la espera (y nunca sabremos si 5 segundos después todo volvería a la normalidad). Internamente se trata de un fallo, por lo general de software, donde un programa no pudi terminar y entró en un ciclo o espera infinita.

Determinar si un algoritmo (ya sea un programa o la  computadora entera) entrará en un ciclo infinito es un problema que es imosible de resolver. De hecho esto se sabe desde 1936, antes de que hubiera computadoras, cuando Alan Turing, el genio inglés y padre de la computación, lo demostró, siendo el primer problema de la clase denominada indecidible (vale la pena leer la biografía de Turing). Se sabe que hay una infinidad de problemas de este tipo. Por fortuna, todos los problemas terrenales con los que nos enfrentamos si tienen solución, aunque sea computacionalmente muy difíciles. En el caso de los problemas más difíciles, es común buscar una solución aproximada en tiempo razonable en vez de una solución perfecta que requiera un tiempo excesivo.