Grosso modo, una Máquina de Turing no es más que una modelización de la computación manual. Esquemáticamente, consiste en una cinta dividida en celdas y una cabeza lectora/escritora que sólo puede realizar una acción en una sola celda por vez.

Pensemos en un algoritmo simple: dado un natural, calcular el siguiente. Operando en binario, todo se reduce a fijar una corta serie de normas sobre cambios entre ceros y unos en función de sus adyacentes, por lo que evidentemente el tiempo que tarde el algoritmo en resolver el problema dependerá de la longitud de la inscripción inicial. Si llamamos n a esa longitud, podemos definir T(n) como el tiempo que tarda en resolver el problema una Máquina de Turing arrancada con una inscripción de tamaño n. T(n) es una función discreta, que se puede intentar acotar mediante una O grande g real.

Si conseguimos acotar el tiempo del algoritmo mediante una O grande que sea a su vez un polinomio real, decimos que es de tiempo polinómico; en caso contrario decimos que el algoritmo es tiempo exponencial. Dándole la vuelta, decimos que un problema es de tiempo polinómico si existe un algoritmo de tiempo polinómico que lo resuelve.

Un problema se dice de decisión si sólo admite dos respuestas. Por ejemplo, la primalidad: un número entero sólo puede ser primo o compuesto. Parece evidente pues llamar P a los problemas de decisión para los que existe un algoritmo de tiempo polinómico que los resuelve. De hecho, desde 2002 sabemos que Primes is in P.

Existe otro tipo de problemas un poco más enrevesados. Consiste en aquellos problemas de decisión para los cuales, si la respuesta es afirmativa, existe un conjunto de valores iniciales y un algoritmo en tiempo polinómico que los resuelve. Nótese la ligera diferencia: si la respuesta es sí y me dan unos datos, lo resuelvo eficientemente. Desde mucho antes de 2002 se sabía que la primalidad es de este tipo… pero haciendo trampa y llamándolo problema de factorización de enteros: dado un número compuesto, si sé es compuesto y tengo unos determinados datos (por ejemplo trivial, un factor) existe un algoritmo de tiempo polinómico que resuelve el problema de factorizarlo (otra cosa es que sea computacionalmente eficiente con las velocidades de las máquinas actuales). Este tipo de problemas se llaman NP (Non-Deterministic Polynomial-time).

La gran pregunta es, por supuesto, ¿P=NP?

No se preocupen, esto es sólo un divertimento… y una cuenta atrás.