Programando con una fotocopiadora

Me habrás oído decir en alguna ocasión, que el problema real que debemos solucionar y su solución, no reside en ningún lenguaje de programación concreto, en todo caso, el tener que usar un lenguaje concreto es una más de las restricciones del problema.

Esta forma de pensar y mi afición al juego de la búsqueda de algoritmos me llevó hace unos tres años a encontrar una curiosa solución al esquivo problema NP-completo, al punto de poder resolverlo en tiempo lineal (sí, coste temporal en O(n)); un gran logro sin duda, si no fuera porque el tamaño de la memoria tiene coste exponencial (¡ouch!, O(eⁿ)).

Aún así, fue emocionante analizar esa posibilidad, porque la solución se basa en utilizar las propiedades de las transparencias y una fotocopiadora para codificar la solución. Si sientes curiosidad por ver cómo tan vetusto aparato puede solucionar tamaño problema te animo a leer Programando con una fotocopiadora.

El problema de la suma de subconjuntos

Un problema muy sencillo de plantear y entender pero muy difícil de resolver, es el problema de la suma de subconjuntos. En él, se trata tan sólo de decir si sí o no es posible sumar una cantidad K con los números C = {z1, z2, …zN} que nos dan.

Por ejemplo, si C = {1, 7, 3} y K = 4 es fácil ver que la respuesta es sí.

Para no salirnos del tema, puedes leer sobre NP-complete. Para el caso que nos ocupa, será suficiente con que sepas que si alguien es capaz de resolver el problema anterior de forma eficiente, será capaz de resolver una gran cantidad de problemas muy importantes de forma eficiente, donde eficiente es resolverlos en tiempo polinomial.

Para que te hagas una idea, hoy en día no es posible encontrar la mejor organización de los componentes electrónicos en una placa (si no sabes nada de electrónica, te sonará que esas placas están llenas de pistas de cobre que van y vienen por todos lados), por ello, se utilizan algoritmos que intentan obtener una buena organización, pero no son capaces de asegurar la mejor organización. Otros muchos e importantes problemas prácticos deben ser aproximados (a veces es suficiente pero otras no) o no pueden ser resueltos y nadie sabe todavía si existe un algoritmo eficiente para resolverlos.

Al menos, se sabe que si alguien demuestra que uno de estos algoritmos no puede resolverse eficientemente, entonces se sabrá que no se puede ninguno (y no habrá que seguir buscando) y más interesante, si alguien demuestra que puede resolver eficientemente uno sólo de estos algoritmos, podrá resolver eficientemente todos estos algoritmos.

Por ahora, no existe mejor solución que (básicamente) ir revisando todas las posibilidades del problema e ir verificando una a una si se cumple o no. Bueno, en realidad (no seamos demasiado laxos), cuando se concreta un problema, siempre se puede hacer alguna mejora. Por ejemplo en el caso del conjunto suma, la mejor solución tiene coste O(2^n/2) que es exponencialmente más eficiente que la trivial, pero sigue siendo exponencialmente más costosa que una polinomial.

Algoritmos y ordenadores

Obviamente cuando diseñamos un algoritmo una de las principales restricciones que tenemos es que debe correr en nuestro ordenador; aunque esta restricción sea obvia, no por ello deja de ser una restricción que podemos considerar eliminar del problema.

Los físicos y en particular ingenieros resuelven diariamente multitud de problemas que podrían definirse como “algoritmos”, un ascensor, unas escaleras mecánicas, los procesos para la elaboración de la lejía, etc… son soluciones que, puestas sobre el papel, se asemejan mucho a las soluciones que definimos los programadores. Una receta de cocina, no deja de ser un algoritmo que es ejecutado por un cocinero.

Puedes estar seguro, que si resuelves el problema NP-complete con una patata y un mondadientes, nadie se va a quejar de que no compila con GCC.

La solución eficiente, de ser encontrada, actuaría directamente en nuestros programas (como una API) o indirectamente como un coprocesador matemático. Muchas personas analizan este tipo de alternativas, en las referencias puedes encontrar una forma usando DNA y es un debate caliente en física la posibilidad de encontrar propiedades cuánticas que puedan ser explotadas para resolver problemas NP-complete.

Las transparencias

Una transparencia es como una hoja de papel pero transparente. Antiguamente (eg. cuando yo estaba en la Universidad) se usaba como sustituto de PowerPoint y similares. Al ser transparentes, se podía fácilmente dibujar por capas las partes de un coche, el cuerpo humano, etc… la forma de verlas, era poner una o varias en un proyector de transparencias.

Resolviendo NP-complete con transparencias y una fotocopiadora

Se trata de ver si dado un conjunto de números, algún subconjunto suma una constante dada. El algoritmo ingenuo es ir revisando todas las formas de agrupar los números y ver si alguna agrupación suma dicha constante. Pero claro, combinaciones de N elementos tomados de 0 en 0, tomados de 1 en 1, …, tomados de N en N hace un total de 2^N agrupaciones, por tanto, en el peor caso, tendremos que revisar un número exponencial de agrupaciones.

Por ejemplo, sean los números { 1, 2, 5, 9, 13 } y el valor que deben sumar sea 15, entonces haríamos:

Iteración	Números que quedan	Libreta
1	{ 1, 2, 5, 9, 13 }	{ 0 }
2	{ 2, 5, 9, 13 }	{ 0, 1 }
3	{ 5, 9, 13 }	{ 0, 1, 2, 3 }
4	{ 9, 13 }	{ 0, 1, 2, 3, 5, 6, 7, 8 }
5	{ 13 }	{ 0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17 }

Es decir, a cada paso, obtenemos el doble de números que la vez anterior porque seguimos dejando los números que teníamos y añadimos esos mismos números pero sumando el elemento que procesamos. Si algunos de los nuevos números es el que buscamos, detenemos el proceso.

¿Y si pudiéramos en cada paso sumar ese nuevo elemento a todos los grupos existentes en un sólo paso (simultáneamente)?, en ese caso, el algoritmo tendría coste lineal, pero resulta que con una transparencia podemos hacer precisamente eso, vemos como:

Algoritmo para la fotocopiadora

Como soporte de almacenamiento, necesitamos un máximo de tantas transparencias como números haya en la lista de entrada. Si nos dan 10 números, necesitaremos 10 transparencias como máximo, si nos dan 100 números tan sólo necesitaremos 100 transparencias como máximo. Fácil ¿no?, incluso conseguir 1000 transparencias no parece nada complicado.

El algoritmo para resolver “SubSet sum” en nuestra fotocopiadora es sencillo:

Todas nuestras transparencias deben tener en la base una línea negra horizontal.
Tomamos la primera transparencia y la ponemos en la fotocopiadora desplazada una longitud linealmente proporcional al primero número.
Hacemos una fotocopia en una transparencia nueva.
Sin quitar la primera transparencia, ponemos la copia realizada desplazándola una longitud linealmente proporcional al segundo número de la lista.
Hacemos una fotocopia en una transparencia nueva.
Sin quitar ni la primera ni segunda transparencias, ponemos la copia realizada desplazándola una longitud linealmente proporcional al tercer número de la lista.
…, y así sucesivamente, repetimos el proceso haciendo tantas copias como números nos hayan dado o bien cuando exista una línea horizontal en la posición linealmente proporcional al valor constante buscado.

El método es tan simple que apenas requiere de explicación. Cada fotocopia que realizamos contiene todos los números anteriores y al desplazarla, estamos sumando todos esos números al del desplazamiento ¡a la vez!.

La solución no es práctica

Probablemente pienses que no es operativo usar unas transparencias y una fotocopiadora, pero ese no es el problema de que el método no sirva en la práctica, los problemas técnicos asociados a la máquina no son tales. Uno puede decir que no es posible hacer una fotocopia cuando en lugar de una hoja tenemos un bloque de (digamos) 30 transparencias, pero este sencillo problema se resuelve haciendo una fotocopia adicional cada pocas (e incluso a cada una, seguiría siendo lineal) fotocopias “desplazadas”. También se puede quejar uno de que no es posible calibrar el desplazamiento que debe hacerse cuando los números son muy grandes (y por tanto el desplazamiento muy pequeño) pero existen elementos para calibrar a nivel atómico. Otros problemas como la dispersión de la luz al atravesar la transparencia o el poder reutilizar el soporte son “sólo” problemas técnicos que de una u otra forma podrían resolverse.

Es obvio que la construcción de la “SubSet Sum Machine” (como yo llamo a la hipotética máquina) distaría de ser la tan sencilla fotocopiadora, sin embargo es notable que su limitación difiere completamente de las limitaciones de los algoritmos actuales (exponenciales en tiempo) pues siempre podrá resolver linealmente cualquier problema en la que la constante K quepa en el dispositivo de almacenamiento (la transparencia).

La limitación real de la máquina consiste en que muchos algoritmos se transforman al problema “subset sum” usando una representación exponencial de K (algo como K = 2^z) y por tanto el tamaño que debe tener la transparencia pasa a ser exponencial. Aunque pudiéramos calibrar nuestra fotocopiadora a nivel atómico y nuestras transparencias fueran una sucesión de átomos de hidrógeno, “sólo” podríamos disponer en cada hoja de aproximadamente 2.970.000.000 átomos, lo que significa que en una hoja sólo podríamos resolver problemas cuya constante K no supere ese valor. Esta limitación hace inútil (o al menos de momento) la solución propuesta.

Conclusión

Además de disfrutar con esta partida en la fascinante búsqueda de algoritmos, han quedado claras las propiedades exponenciales del problema NP-completo analizado. Si estás interesado en profundizar en las propiedades de tamaño problema y el estado del arte del mismo, te sugiero a un gigante en la materia, David Pisinger, con su artículo Where are the hard knapsack problems? (son sólo 14 páginas).

¡Eh! ¿y que pasa si yo lo resuelvo?

Bueno, en otras disciplinas como las matemáticas (en las que tendrías que convencer a gente sesuda que lea tu trabajo) o en física (tendrías que conseguir inversores que te financien el desarrollo) sería complicado hacer valer tu trabajo o tendrías que revelar tu descubrimiento. Afortunadamente, si eres capaz de resolver eficientemente un problema NP-completo, podrás fácilmente colgar una página web en la que cualquiera pueda postear un problema muy difícil para tu algoritmo (elige alguno de entre 3SAT, TSP, Knapsack, etc…) y dile en cuanto tiempo lo tendrá resuelto (antes habrás analizado empíricamente el coste real de tu algoritmo para hacer predicciones precisas). Sin revelar tu poderoso algoritmo, convencerás al mundo de su valía y el dinero empezará a caer sobre tu cabeza.

Como diversión, está bien pensar que quizás lo resuelvas, pero advertido quedas de que se cree que tal solución no existe y por tanto, estarías buscando la piedra filosofal…

Más información | Where are the hard knapsack problems?.
Más información | NP-completo.
Más información | Problema de la suma de subconjuntos.
Más información | Using DNA algorithms to solve NO-complete problems.