Los intratables de la Computación

Los de arriba son Los Intocables de Eliot Ness, gran película de Brian de Palma, estrenada en 1987 con Kevin Costner, Sean Connery, De Niro, Andy García, Charles Martin Smith, .. (actorazos) y demás, pero, algunos dirán, ¿qué pinta esto aquí? Pues pinta porque el título del post se parece al de la película y cómo hablaremos de cuatro problemas y los intocables también eran cuatro, pues todo cuadra. Luego explicaré las siglas que le he puesto a cada uno en la imagen de arriba (tiene sentido, lo prometo). Pues eso, en este post vamos a tratar de los problemas intratables en la Computación y cómo la IA ayuda a solucionarlos. Empezamos!

Problemas en Computación hay muchos y de eso se trata, de que hayan problemas para que se puedan resolver con la ayuda de un ordenador. Sin embargo, hay algunos que ponen a prueba las capacidades tecnológicas de las que disponemos y nuestro ingenio matemático. Estos son los problemas intratables, un conjunto de enigmas computacionales que han fascinado y frustrado también a muchos investigadores durante décadas. En este artículo nos vamos a sumergir en desentrañar los secretos de estos problemas.

Las características de un problema para que sea catalogado como intratable son:

1. Complejidad exponencial. Esto significa que el tiempo o espacio necesario para resolver el problema crece muy rápidamente a medida que aumenta el tamaño de la entrada. Por ejemplo, si para un problema con 10 elementos de entrada se necesitan 2¹⁰ = 1,024 pasos, para 20 elementos se necesitarían 2²⁰ = 1,048,576 pasos, y para 30 elementos, 2³⁰ = 1,073,741,824 pasos. Este crecimiento explosivo hace que el problema sea prácticamente irresoluble para entradas grandes.
2. No se conoce solución eficiente. Un algoritmo eficiente es aquel que resuelve el problema en tiempo polinomial, es decir, el tiempo de ejecución crece como una potencia del tamaño de la entrada (n², n³, etc.). Para los problemas intratables, no se ha encontrado (y se cree que no existe) un algoritmo que los resuelva en tiempo polinomial para todos los casos posibles.
3. Omnipresentes. Estos problemas aparecen en muchas disciplinas diferentes. Por ejemplo, en logística, en diseño de circuitos, en asignación de recursos, en finanzas, y muchos más. Su ubicuidad los hace especialmente relevantes e importantes ya que son complicados de resolver pero importantes en diferentes sectores.
4. Importancia teórica y práctica. El estudio de estos problemas ha llevado a desarrollos importantes en la teoría de la complejidad computacional, como la definición de las clases de complejidad P y NP.

Resolvamos el misterio del principio. En la imagen inicial veíamos a Andy, Sean, Kevin y Charles todos puestos para derrotar a los gángsters. Pero a cada uno le había puesto una palabreja que lo identificaba. Pues resulta que cada una de las siglas pertenece a un ejemplo de problema intratable (ingenioso, ¿verdad?). Veamos los cuatro ejemplos de los intratables de la Computación:

1. El problema del viajante (TSP). Imaginemos un vendedor que debe visitar 20 ciudades en un tiempo determinado para vender un producto, pero empezando y acabando en la misma ciudad y se quiere saber cuál es la ruta más corta posible. Si esto es así, el vendedor puede coger una ruta de entre 20! (20 factorial) = 2,432,902,008,176,640,000 posibles rutas, es decir, un número enorme (más que enorme). Por eso, es un problema intratable. Incluso si un ordenador pudiera evaluar un millón de rutas por segundo, tardaría más de 77 años en examinarlas todas. Esta explosión combinatoria hace que el TSP sea intratable para un gran número de ciudades. El pobre Andy se queda sin solución.
2. El problema de la satisfacibilidad booleana (SAT). Supongamos que tenemos una fórmula booleana como: (A OR B) AND (NOT A OR C) AND (B OR NOT C). El problema SAT consiste en determinar si existe alguna asignación de valores verdadero/falso a A, B y C que haga que toda la fórmula sea verdadera. Para n variables, hay 2ⁿ posibles asignaciones, lo que hace que el problema sea intratable para fórmulas con muchas variables, es decir, ya no con sólo tres variables, sino con cinco o más. El amigo Sean no puede resolverse.
3. El problema de la coloración de grafos (GCP). Pensemos en un mapa con 50 regiones. Necesitamos colorear cada región de manera que ninguna región adyacente tenga el mismo color, usando el menor número de colores posible. ¿Complicado, no? El número de formas posibles de colorear el mapa crece exponencialmente con el número de regiones, haciendo que este problema sea intratable para mapas grandes o grafos complejos. No se encuentra la solución para el míster, Kevin.
4. El problema de la mochila (Knapsack Problem, KSP). Ahora imagina que tienes una mochila que puede llevar 50 kg y 100 objetos diferentes, cada uno con un peso y un valor. Supón que quieres maximizar el valor total de los objetos en la mochila sin exceder el límite de peso. Con este escenario, resulta que hay 2¹⁰⁰ combinaciones posibles de objetos, un número astronómicamente grande que hace que el problema sea intratable para un gran número de objetos. Charles es intratable, imposible (¿seguro?) de solucionar.

Estos cuatro ejemplos nos enseñan cómo, a medida que el tamaño de la entrada aumenta, el número de posibles soluciones crece exponencialmente, haciendo que sea computacionalmente inviable examinar todas las posibilidades para encontrar la solución óptima en un tiempo razonable. Ahora bien, si son problemas intratables, ¿qué hacemos? ¿Los dejamos ahí sin solucionar? No…, esa no es la idea. La idea es que tengan solución o que podamos lidiar con ellos de alguna forma. Sigamos.

Aunque no podemos resolver eficientemente los problemas intratables en su forma general, existen varias estrategias para lidiar con ellos. Estas estrategias son los algoritmos de aproximación, los métodos heurísticos, los algoritmos de tiempo subexponencial o la computación cuántica. Sin embargo, el nuevo jugador en el terreno de juego que puede ayudarnos a conseguir mejoras en estos problemas es bien conocido por todos, la Inteligencia Artificial.

La IA ha emergido como una herramienta poderosa para abordar problemas intratables, ofreciendo nuevas perspectivas y soluciones innovadoras:

1. Aprendizaje automático. Los algoritmos de aprendizaje automático pueden identificar patrones y estructuras en los datos que ayudan a reducir el espacio de búsqueda en problemas combinatorios.
2. Redes neuronales. Las redes neuronales profundas han demostrado ser eficaces en la aproximación de soluciones para problemas de optimización complejos, como el TSP.
3. Optimización basada en IA. Técnicas como los algoritmos genéticos y la optimización por enjambre de partículas se inspiran en procesos naturales y pueden encontrar soluciones de alta calidad para problemas intratables.
4. Sistemas híbridos. La combinación de técnicas de IA con métodos tradicionales de optimización ha llevado a algoritmos más eficientes para abordar problemas NP-duros.
5. Aprendizaje por refuerzo. Este enfoque de IA ha mostrado resultados prometedores en la resolución de problemas de planificación y toma de decisiones complejas.
6. IA explicable. Los avances en IA explicable están ayudando a comprender mejor las soluciones propuestas por los sistemas de IA, lo que es crucial en dominios donde la interpretabilidad es importante.
7. Computación neuromórfica. Esta nueva arquitectura de computación inspirada en el cerebro promete abordar ciertos problemas intratables de manera más eficiente que los ordenadores tradicionales.

Los problemas intratables representan una frontera fascinante en la ciencia de la computación. Aunque siguen desafiando nuestras capacidades computacionales, su estudio ha llevado a desarrollos significativos en algoritmos, teoría de la complejidad y técnicas de optimización. A medida que avanzamos hacia nuevos paradigmas computacionales, como la IA, es posible que encontremos nuevas formas de abordar estos problemas aparentemente insolubles, abriendo nuevas posibilidades en la resolución de problemas complejos en diversos campos de la ciencia y la ingeniería. Por tanto, es posible que, con estos avances en la IA, los problemas intratables lo sean un poco menos y nuestros amigos Andy, Sean, Kevin y Charles (o más bien, TSP, SAT, GCP y KSP) puedan solucionarse.

Referencias

Arora, S., & Barak, B. (2009). Computational complexity: A modern approach. Cambridge University Press.

Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman and Company.

Papadimitriou, C. H. (2003). Computational complexity. John Wiley & Sons.

Vazirani, V. V. (2013). Approximation algorithms. Springer Science & Business Media.

Woeginger, G. J. (2003). Exact algorithms for NP-hard problems: A survey. In Combinatorial optimization—eureka, you shrink! (pp. 185-207). Springer.