Matías es un alumno de Introducción a la Programación. Para su primera tarea tiene que desarrollar un programa que escriba un número 1 en la consola. Con dos semanas de plazo para entregar, Matías —un alumno brillante— se relaja y decide aventurarse por una estrategia original. Probará todas las posibles secuencias de caracteres de largo 1, luego de largo 2, y así sucesivamente, hasta que una de ellas haga lo que pide el enunciado. De esta manera, él entregará el programa más corto posible que resuelve el problema (lo cual es motivo de orgullo).

Para conseguirlo cuenta con computadores, cada uno con la capacidad de verificar posibles programas por segundo (no me pregunten de dónde los sacó, sólo sabemos que los tiene). Llamemos al tiempo que tardarán todos estos computadores en verificar todos los programas de largo (es decir, que tienen caracteres en total). Suponiendo que Matías puede usar 256 caracteres para programar, tiene en total posibles programas de largo . Así, el tiempo que tardará en verificarlos está dado por

Supongamos ahora que en cada electrón del universo tenemos un supercomputador que realiza de estas verificaciones por segundo. La cantidad estimada de electrones del universo es , por lo que

Ahora bien, el siguiente programa en Java escribe el número 1 en la consola. Tiene 96 caracteres.

public class Principal
{
  public static void main(String[] args) {
    System.out.println(1);
  }
}

Si eliminamos los saltos de línea innecesarios lo podemos dejar en 86 caracteres. Asumamos que éste es el programa de menor largo que es solución al enunciado.

public class Principal{public static void main(String[] args){System.out.println(1);}}

Para llegar a verificar los programas de largo 86, Matías debe verificar primero todos los de largo 85 (y darse cuenta de que ninguno le servía). En total hay programas que verificar (es decir, exponencial respecto del largo del programa). Así, para tenemos que

Como , entonces

La edad estimada del universo es de 13.600 millones de años, y eso es . Esto significa que para verificar todos los programas de largo 85, Matías tardará segundos, ¡más que la edad del universo!

¿Se van imaginando cuánto tiempo tardaría —con todo ese poder computacional— si el programa más corto que le sirve tuviera unas 200 líneas de código (que es algo más razonable que 85)?

Este simple ejemplo justifica un poco la elección del apodo “ineficiente” para los algoritmos de tiempo exponencial. Se sabe que los problemas de la clase NP pueden ser resueltos de manera determinista en tiempo a lo más exponencial (como el problema de Matías). Lo que no se sabe es si cada uno de ellos además se puede resolver en tiempo polinomial de manera determinista (P).

El problema de P y NP es uno de los más importantes en computación teórica, y ciertamente el más importante en el área de Complejidad Computacional. Tan importante es (y tan difícil), que es uno de los siete problemas por cuya solución el Instituto de Matemáticas Clay ofrece un millón de dólares.

Habrá que ponerse a estudiar.