Con el poder de las tecnologías de inteligencia artificial, las computadoras actualmente pueden entablar conversaciones convincentes con las personas, componer canciones, pintar cuadros, jugar al ajedrez y diagnosticar enfermedades, por nombrar solo algunos ejemplos de su destreza tecnológica.

Estos éxitos podrían tomarse como una indicación de que la computación no tiene límites. Para ver si ese es el caso, es importante comprender qué hace que una computadora sea poderosa.

Hay dos aspectos en el poder de una computadora: la cantidad de operaciones que su hardware puede ejecutar por segundo y la eficiencia de los algoritmos que ejecuta.

La velocidad del hardware está limitada por las leyes de la física. Los algoritmos, básicamente un conjuntos de instrucciones, son escritos por humanos y se traducen en una secuencia de operaciones que el hardware de la computadora puede ejecutar. Incluso si la velocidad de una computadora pudiera alcanzar el límite físico, los obstáculos computacionales permanecen debido a los límites de los algoritmos.

Estos obstáculos incluyen problemas que son imposibles de resolver para las computadoras y problemas que son teóricamente solucionables, pero que en la práctica están más allá de las capacidades incluso de las versiones más poderosas de las computadoras actuales imaginables.

Los matemáticos y los informáticos intentan determinar si un problema tiene solución probándolos en una máquina imaginaria.

Una máquina de computación imaginaria

La noción moderna de algoritmo, conocida como máquina de Turing, fue formulada en 1936 por el matemático británico Alan Turing. Es un dispositivo imaginario que imita cómo se realizan los cálculos aritméticos con un lápiz sobre papel. La máquina de Turing es la plantilla en la que se basan todas las computadoras de hoy.

Para acomodar los cálculos que necesitarían más papel si se hicieran manualmente, se supone que el suministro de papel imaginario en una máquina de Turing es ilimitado. Esto es equivalente a una cinta ilimitada imaginaria llena de cuadrados, cada uno de los cuales está en blanco o contiene un símbolo.

La máquina está controlada por un conjunto finito de reglas y comienza con una secuencia inicial de símbolos en la cinta. Las operaciones que puede realizar la máquina son moverse a una casilla vecina, borrar un símbolo y escribir un símbolo en una casilla en blanco. La máquina calcula realizando una secuencia de estas operaciones. Cuando la máquina termina, o se “detiene”, los símbolos que quedan en la cinta son la salida o el resultado.

La informática a menudo se trata de decisiones con respuestas de sí o no. Por analogía, una prueba médica (tipo de problema) verifica si la muestra de un paciente (una instancia del problema) tiene un determinado indicador de enfermedad (respuesta sí o no). La instancia, representada en una máquina de Turing en forma digital, es la secuencia inicial de símbolos.

Un problema se considera “soluble” si se puede diseñar una máquina de Turing que se detenga para cada instancia, ya sea positiva o negativa, y determine correctamente qué respuesta produce la instancia.

No todos los problemas se pueden resolver

Muchos problemas se pueden resolver con una máquina de Turing y, por lo tanto, se pueden resolver en una computadora, mientras que muchos otros no.

Por ejemplo, el problema del dominó, una variación del problema de mosaico formulado por el matemático chino-estadounidense Hao Wang en 1961, no tiene solución.

La tarea es usar un conjunto de fichas de dominó para cubrir una cuadrícula completa y, siguiendo las reglas de la mayoría de los juegos de dominó, igualar el número de puntos en los extremos de las fichas de dominó contiguas. Sin embargo, no existe ningún algoritmo que pueda comenzar con un conjunto de fichas de dominó y determinar si el conjunto cubrirá o no completamente la cuadrícula.

Manteniéndolo razonable

Una serie de problemas solucionables pueden resolverse mediante algoritmos que se detienen en un período de tiempo razonable. Estos “algoritmos de tiempo polinomial” son algoritmos eficientes, lo que significa que es práctico usar computadoras para resolver instancias de ellos.

No se sabe que miles de otros problemas solucionables tengan algoritmos de tiempo polinomial, a pesar de los intensos esfuerzos en curso para encontrar tales algoritmos. Estos incluyen al problema del vendedor viajero (Travelling Salesman Problem o TSP).

El TSP pregunta si un conjunto de puntos con algunos puntos conectados directamente, llamado gráfico, tiene un camino que comienza en cualquier punto, pasa por todos los demás puntos exactamente una vez y regresa al punto original. Imagina que un vendedor quiere encontrar una ruta que pase por todos los hogares de un vecindario exactamente una vez y regrese al punto de partida.

Estos problemas, llamados NP-completos, fueron formulados de forma independiente y demostraron existir a principios de la década de 1970 por dos científicos informáticos, el canadiense-estadounidense Stephen Cook y el estadounidense-ucraniano Leonid Levin.

Cook, cuyo trabajo llegó primero, recibió el Premio Turing de 1982, el más alto en informática, por este trabajo.

El costo de saber exactamente

Los algoritmos más conocidos para problemas NP-completos buscan esencialmente una solución a partir de todas las respuestas posibles. El problema del vendedor viajero en un gráfico de unos pocos cientos de puntos tardaría años en ejecutarse en una supercomputadora. Dichos algoritmos son ineficientes, lo que significa que no hay atajos matemáticos.

Los algoritmos prácticos que abordan estos problemas en el mundo real solo pueden ofrecer aproximaciones, aunque las aproximaciones están mejorando. La existencia de algoritmos de tiempo polinomial eficientes que puedan resolver problemas NP-completos se encuentran entre los siete problemas abiertos del milenio publicados por el Clay Mathematics Institute a principios del siglo XXI, cada uno con un premio de 1 millón de dólares.

Más allá de Turing

¿Podría haber una nueva forma de computación más allá del marco de Turing? En 1982, el físico estadounidense Richard Feynman, premio Nobel, planteó la idea de la computación basada en la mecánica cuántica.

En 1995, Peter Shor, un matemático aplicado estadounidense, presentó un algoritmo cuántico para factorizar números enteros en tiempo polinomial. Los matemáticos creen que esto no se puede resolver mediante algoritmos de tiempo polinomial en el marco de Turing. Factorizar un entero significa encontrar un entero más pequeño mayor que 1 que pueda dividir el entero. Por ejemplo, el entero 688.826.081 es divisible por el entero menor 25.253, porque 688.826.081 es igual a 25.253 por 27.277.

Un algoritmo principal llamado algoritmo RSA, ampliamente utilizado para proteger las comunicaciones de red, se basa en la dificultad computacional de factorizar números enteros grandes. El resultado de Shor sugiere que la computación cuántica, si se hace realidad, cambiará el panorama de la ciberseguridad.

¿Se puede construir una computadora cuántica completa para factorizar números enteros y resolver otros problemas? Algunos científicos creen que puede ser. Varios grupos de científicos de todo el mundo están trabajando para construir una y algunos ya han construido computadoras cuánticas a pequeña escala.

Sin embargo, como todas las tecnologías novedosas inventadas antes, es casi seguro que surgirán problemas con la computación cuántica que impondrían nuevos límites.

* Jie Wang es profesor de Ciencias de la Computación en la Universidad de Massachusetts Lowell.

** Este artículo se republicó desde The Conversation bajo una licencia Creative Commons. Lea el artículo original en inglés.