En primer lugar, una máquina de Turing es un objeto matemático cuya definición requiere algo de trabajo previo. Un profano puede leer algoritmo en lugar de máquina de Turing porque una máquina de Turing es, literalmente, eso: la formalización matemática del concepto de algoritmo en la tesis de Church (un algoritmo ES una máquina de Turing), motivada por el planteamiento del Problema X de Hilbert. Total, que cuando ponga máquina de Turing, se puede leer algoritmo.
En segundo lugar, cuando hablemos de problemas en P, o en NP, o NP-completos, nos referiremos a problemas de decisión: problemas en los que el output del algoritmo puede ser SÍ o NO. Por ejemplo, el problema de decidir si un número entero es primo o no es un problema de decisión. El problema de saber si un grafo es $k$-coloreable es un problema de decisión. No son problemas de decisión encontrar los factores primos de un número entero, o encontrar una coloración de un grafo. El motivo es que las clases de complejidad de los problemas de decisión están mejor estudiadas en general.
Uno de los elementos principales de una máquina de Turing es su función de transición, mal llamada "función" porque no tiene por qué ser una función. La función de transición es lo que se conoce en matemáticas como una correspondencia. Una correspondencia entre dos conjuntos $X$ e $Y$ no es más que cualquier subconjunto no vacío del producto cartesiano $X \times Y$. Se puede ver también como un grafo bipartito dirigido "de izquierda a derecha", o, incluso, más informalmente, como una "función" en la que se admite que haya elementos que no tengan imagen o elementos que tengan varias imágenes. La función de transición de una máquina de Turing contiene las instrucciones de lo que la máquina debe hacer en cada momento: a la izquierda tenemos un conjunto que contiene el estado de la máquina en un momento determinado y la información de lo que lee en la cinta. A la derecha tenemos el nuevo estado que debe adoptar la máquina. Por ejemplo, si la máquina está sumando números y lee un $2$ y un $3$, la función de transición le dice a la máquina que tiene que escribir un $5$ en la cinta de output. Puede resultar un poco rara al principio la idea de que la máquina pueda no hacer nada o hacer varias cosas en un instante determinado, pero formalmente el uso de las correspondencias no presenta ningún problema.
Las máquinas de Turing en las que la función de transición es una aplicación propiamente dicha (todos los elementos del dominio tienen una y sólo una imagen) se llaman deterministas. El nombre tiene sentido: dado un input, podemos seguir el camino marcado por la función de transición de la máquina y en cada instante sabemos que la máquina hará algo y que sólo hay una posibilidad para ese algo, de modo que el output queda determinado por el input, lo que no ocurre en general con las máquinas de Turing no deterministas (máquinas de Turing de las que sólo sabemos que su función de transición es una correspondencia). La clase de complejidad P consiste en todos aquellos problemas de decisión que pueden ser resueltos en tiempo polinomial por una máquina de Turing determinista. La clase de complejidad NP consiste en todos aquellos problemas de decisión que pueden ser resueltos en tiempo polinomial por una máquina de Turing (no determinista). Como toda máquina de Turing determinista es, en particular, no determinista (toda aplicación es, en particular, una correspondencia), obviamente P $\subseteq$ NP.
Ahora bien, ¿por qué se dice eso de que NP son los problemas cuyas soluciones son fáciles de comprobar en lugar de contar todo este rollo de las máquinas deterministas y no deterministas? Pues porque hay una caracterización de los problemas NP en estos términos: un problema está en NP si, y sólo si, admite un verificador polinomial. Pongamos que $A$ es un problema NP. Por definición, existe una máquina de Turing no determinista $M$ que resuelve $A$ en tiempo polinomial. Ahora bien, esto es equivalente (teorema) a que exista una máquina de Turing determinista $V$ tal que para todo input $x$ para el que $M$ devuelve SÍ, existe un $c$ (llamado certificado), de tal modo que $V$ devuelve SÍ con input $(x,c)$. La versión de esta caracterización cambiando SÍ por NO es lo que define a la clase de complejidad co-NP. Por ejemplo, el problema PRIMES (dado un número natural $n$, decidir si $n$ es primo o no) está en co-NP porque si $n$ no es primo, entonces tiene un certificado (dos factores propios), y se puede comprobar en tiempo polinomial que ambos factores dividen a $n$. Además, PRIMES también está en NP (hoy conocemos el test de primalidad AKS que sirve como verificador, pero antes de eso ya se habían construido certificados para la primalidad basados en el Pequeño Teorema de Fermat). Así que PRIMES $\in$ NP $\cap$ co-NP.
Los problemas NP-completos son aquellos que conforman la "frontera de lo intratable". Decimos que un problema $A$ se reduce (en el sentido de Karp) a un problema $B$, si existe una máquina de Turing determinista que, en tiempo polinomial, traduce entradas de $A$ en entradas de $B$. Se escribe $A \leq B$. Un problema $A$ es NP-completo si $A$ está en NP y todo problema NP puede reducirse a él. Con la notación de antes, para todo $B \in$ NP, $B \leq A$. Por esto, en el típico diagrama de Venn de P y NP, pueden verse los problemas NP como problemas en la frontera de NP.
Primera cuestión después de introducir una definición ¿hemos dado una definición exótica del conjunto vacío? Es decir, ¿existe algún problema NP-completo? La respuesta es el Teorema de Cook: el problema SAT de satisfacibilidad booleana (saber si una fórmula con variables, ands ors y nots se satisface para algunos valores concretos de las variables) es NP-completo. A partir de este teorema se puede demostrar que muchos otros problemas son también NP-completos. Si dado un problema $A$ demostramos que $A$ está en NP y que SAT $\leq$ A, habremos demostrado que $A$ es NP-completo por transitividad de la relación $\leq$. Por ejemplo, para demostrar que $3$-COLOR (decidir si un grafo es $3$-coloreable) es NP-completo puede encontrarse una reducción explícita de SAT a $3$-COLOR. La relación $\leq$ establece, en cierto sentido, una equivalencia entre todos los problemas NP-completos porque cualquiera de ellos se puede reducir en tiempo polinomial a cualquier otro. La Conjetura de Cook (o problema P vs. NP) se pregunta cuál es la relación entre P y NP. Para demostrar que P $\neq$ NP hay que encontrar un problema en NP $ \setminus$ P, o sea, un problema que pueda ser resuelto en tiempo polinomial por una máquina de Turing no determinista (o que sus soluciones se verifican rápidamente), y probar que no puede ser resuelto en tiempo polinomial por una máquina de Turing determinista. Para probar que P $=$ NP, basta encontrar un algoritmo determinista que resuelva en tiempo polinomial algún problema NP-completo de esta lista. Si se encuentra, cualquier problema NP puede reducirse en tiempo polinomial al problema NP-completo y, posteriormente, ser resuelto en tiempo polinomial por el algoritmo. Por ejemplo, si existe un algoritmo que, en tiempo polinomial, permita decidir si un grafo es $3$-coloreable, entonces P $=$ NP.
Para terminar, diré que la Conjetura de Cook es sólo la punta del iceberg de todo lo que no sabemos sobre las relaciones entre las clases de complejidad. A modo de ejemplo, podemos ver el diagrama de relaciones entre las clases de complejidad que elaboró un profesor mío para una charla. Cada ? del diagrama es un problema abierto.
No hay comentarios:
Publicar un comentario