Clases de complejidad y P vs. NP#
Introducción#
Los problemas algorítmicos están clasificados en clases de complejidad de acuerdo al algoritmo más rápido que conocemos para resolverlos. En este capítulo hablaremos de algunas de las clases de complejidad más famosas: P, NP, NP-completo y NP-difícil. La primera es la de los problemas que podemos responder rápido. La segunda es de los problemas cuya solución podemos verificar rápido. Las últimas dos son clases de problemas que al resolverlos rápido podríamos resolver cualquier otro en NP. Esto nos llevará al problema abierto en teoría computacional más importante: P vs. NP.
Las clase de complejidad P#
Todo lo que discutiremos en estas secciones se refiere a problemas de decisión. Como platicamos anteriormente, podemos pensar a los problemas de decisión como aquellos en los cuales la respuesta es sí o no. Aunque de momento nos limitaremos a esa clase de problemas, hay maneras de extender lo que discutimos a otro tipo de problemas algorítmicos.
La clase de complejidad \(P\) consiste de aquellos problemas algóritmicos que podemos resolver en tiempo polinomial. Por eso la letra \(P\). Con esto nos referimos a que para ellos debe existir un entero \(k \geq 0\) y un algoritmo tal que cualquier instancia de tamaño \(n\) la resuleva en tiempo \(O(n^k)\).
En el transcurso de este libro hemos encontrado varios problemas que están en la clase \(P\), por ejemplo:
Dado un conjunto de \(n\) números, ver si hay dos de ellos con suma igual a un número dado \(M\). El problema está en \(P\) pues un algoritmo trivial que verifica todas las \(\binom{n}{2}\) parejas corre en tiempo \(O(n^2)\). De hecho, ya vimos que se puede mejorar este tiempo, pues dimos un algoritmo que corre en tiempo \(O(n\log n)\).
En general, si tenemos un entero \(k\geq 0\) fijo, ver si dados \(n\) números hay \(k\) de ellos cuya suma es igual a un número dado \(M\). Está en la clase \(P\) pues para resolverlo en tiempo \(O(n^k)\) basta verificar cada una de las \(\binom{n}{k}\) posibilidades de subconjuntos de \(k\) elementos.
Dada una gráfica en \(n\) vértices, decir si hay un camino entre dos vértices o no. Está en \(P\) pues podemos hacer BFS o DFS en tiempo \(O(n+m)=O(n^2)\). De hecho, ver si la gráfica es conexa también está en \(P\).
Dada una lista de \(n\) números, saber si hay dos de ellos repetidos. La forma en la que resolvimos esto fue ordenando los números y viendo con una lectura lineal si en la lista ordenada hay dos iguales. Esto toma tiempo \(O(n\log n)\), que también es \(O(n^2)\).
Dada una gráfica en \(n\) vértices, saber si hay dos de ellos a distancia \(100\). También está en \(P\) pues el algoritmo de Floyd-Warshall nos permite calcular todas las distancias en tiempo \(O(n^3)\), y luego en tiempo \(O(n^2)\) podemos ver si alguna de ellas fue \(100\).
La clase de complejidad NP#
La clase de complejidad \(NP\) es algo distinta. Son aquellos problemas cuya respuesta «sí» se puede verificar en tiempo polinomial. Siendo un poco más precisos, lo que esperamos de los problemas en \(NP\) es que cada que la respuesta sea «sí» haya un objeto testigo que testifique que la respuesta sea «sí» y un algoritmo verificador que verifique la correctitud del testigo en tiempo polinomial. Es un poco más fácil entender esto mediante problemas ejemplo.
Para empezar, es fácil convencerse de que todos los problemas que mencionamos arriba están en la clase \(NP\). Argumentemos eso para algunos como primeros ejemplos.
En el problema de dar dos números cuya suma sea \(M\), lo que podemos usar para poder responder «sí» como testigo es a dichos dos números \(a\) y \(b\). Un algoritmo verificador puede en tiempo \(O(1)\) sumar estos dos números y darse cuenta de que en efecto suman \(M\) (o no).
En el problema de decir si una gráfica es conexa, lo que podemos usar para poder responder «sí» como testigo es una lista de caminos entre cualesquiera dos vértices. Un algoritmo verificador puede tomar cada uno de estos \(\binom{n}{2}\) caminos y en tiempo \(O(n)\) ver si son caminos válidos, verificando que en efecto consistan de aristas de la gráfica.
De hecho, después de pensarlo un poco no es difícil convencerse de que todos los problemas que están en \(P\) también están en \(NP\). Sin embargo, lo opuesto no es nada claro: si podemos verificar rápido la respuesta, ¿será que podemos resolver rápido el problema? No lo sabemos. Hay problemas que están en NP, pero que nadie sabe si están en la clase P. Veamos algunos ejemplos.
Ejemplo. El problema suma de subconjuntos pregunta lo siguiente: «Dado un conjunto \(X\) de \(n\) números, ver si hay algunos de ellos con suma \(M\).»
Veamos que está en la clase \(NP\). Para poder responder que sí, podemos usar como testigo un subconjunto \(Y\subseteq X\) con suma igual a \(M\). Como \(Y\) tiene a lo más \(n\) números, un algoritmo verificador puede sumarlos en tiempo \(O(n)\) y decirnos si es un testigo válido o no. Entonces, es rápido verificar soluciones.
Pero, ¿es rápido resolver el problema? Un algoritmo inocente recorrería todos los subconjuntos de \(X\) para ver si la suma de los elementos de alguno es \(M\). Esto tomaría tiempo \(\Theta(2^n)\). ¿Podemos hacerlo más rápido? En esencia, nadie sabe. Los mejores algoritmos que se conocen corren en tiempo exponencial en \(n\). En particular, nadie sabe si puede responderse en tiempo polinomial.
\(\square\)
Ejemplo. El problema trayectoria hamiltoniana pregunta lo siguiente: «Dada una gráfica, encontrar si hay una trayectoria que pase por todos los vértices».
El problema está en \(NP\). Un testigo de la respuesta «sí» es el orden en el que se recorren los vértices. Un algoritmo verificador puede irla recorriendo. Si en algún momento pasa por más de \(n\) vértices, ya no es trayectoria. Si tiene \(n\) o menos, entonces en tiempo \(O(n)\) puede ver si en efecto se usan las aristas de la gráfica de manera válida, y en tiempo \(O(n\log n)\) que no se repitan vértices.
Así, verificar un testigo es rápido pero, ¿resolver el problema? Un algoritmo inocente sería probar con cada una de las \(n!\) formas de recorrer los vértices y ver si en efecto pasan por aristas de la gráfica. Esto tarda mucho, pues toma tiempo \(\Theta(n!)\). ¿Se podrá bajar a tiempo polinomial? Nadie sabe.
\(\square\)
Ejemplo. Veamos un último ejemplo, que viene de la lógica. Se llama el problema 3-SAT. Tomemos \(x_1,\ldots,x_n\) variables binarias (pueden ser falsas o verdaderas). Tomemos una expresión del siguiente estilo:
Aquí cada \(a_{ij}\) es alguna variable \(x_k\) o su negación. A cada \((a_{j1}\lor a_{j2} \lor a_{j3})\) le llamamos una cláusula.
Estamos pensando que la expresión ya está simplificada, es decir, que no hay cláusulas redundantes. Notemos que entonces \(m\) es como mucho \(8\binom{n}{3}\): como mucho podemos tener tantas cláusular como formas de elegir \(3\) variables, y para cada una de ellas hay \(8\) formas de elegir cuáles están negadas y cuáles no.
¿Podremos dar una asignación de verdad a las variables \(x_1,\ldots,x_n\) de modo que la expresión en total sea verdadera?
Este es un problema en NP pues un testigo sería la asignación de verdad que funciona. Como hay a lo mucho \(8\binom{n}{3}\) cláusulas, podemos verificar si en efecto la expresión evalúa a verdadero en tiempo \(O(n^3)\).
Pero, suena muy difícil encontrar dicha asignación. Hay \(2^n\) formas de hacer asignaciones para las \(n\) variables y pasar por todas tomaría tiempo \(O(2^n)\). ¿Se puede encontrar una asginación en tiempo polinomial? Nadie sabe.
\(\square\)
Reducciones y la clases NP-completo y NP-difícil#
Queremos hablar de otras dos clases computacionales más, pero para ello necesitamos unas pocas definiciones. La siguiente definición refleja la idea de cuándo podemos usar un problema para resolver otro.
Definición. Dados problemas algorítmicos \(A\) y \(B\), vamos a decir que existe una reducción del problema \(A\) al problema \(B\) si podemos pasar (algoritmicamente) cualquier instancia \(I\) del problema \(A\), a una instancia \(\varphi(I)\) del problema \(B\), con la propiedad de que la respuesta para \(I\) en \(A\) es «sí» si y sólo si la respuesta para \(\varphi(I)\) en \(B\) es «sí».
Cuando hay una reducción de \(A\) a \(B\) podemos usar a \(B\) como subrutina para resolver \(A\). Supongamos que una instancia de tamaño \(n\) de \(A\) pasa a una de tamaño a lo más \(T(n)\) de \(B\) en tiempo \(g(n)\). Supongamos que las instancias de \(B\) de tamaño \(n\) se pueden resolver en tiempo \(f(n)\). Entonces podemos resolver una instancia de \(A\) de tamaño \(n\) en \(g(n)+f(T(n))\) pasos.
Supongamos por el momento que el tamaño de intancia de la reducción no crece mucho y sigue siendo \(O(n)\). Supongamos también que hacer el cambio de instancia es muy rápido, menos de lo que tarda resolverla en \(B\). Entonces \(g(n)+f(T(n))=O(f(n))\). Tenemos entonces intuitivamente que «si \(B\) se puede resolver rápido, entonces \(A\) se puede resolver rápido». La contrapositiva es muy interesante también: «si tenemos la garantía de que \(A\) no se puede resolver rápido, entonces \(B\) tampoco se puede resolver rápido». Esto da un método para encontrar cotas inferiores para el tiempo de resolución de ciertos problemas algorítmicos.
Para definir la clase \(NP\), nos interesa una definición un poco más restrictiva de reducción.
Definición. Diremos que hay una reducción polinomial de \(A\) a \(B\) si hay una reducción del problema \(A\) al problema \(B\) en donde además se cumple que hay enteros positivos \(k\) y \(\ell\) tales que para cualquier instancia \(I\) de \(A\):
Obtener \(\varphi(I)\) toma tiempo \(O(|I|^k)\).
La instancia \(\varphi(I)\) tiene tamaño \(O(|I|^\ell)\).
La discusión anterior nos lleva a lo siguiente.
Observación. Si hay una reducción polinomial de \(A\) a \(B\), y \(B\) está en la clase de complejidad \(P\), entonces \(A\) también está en la clase de complejidad \(P\).
Estamos listos para definir las dos últimas clases que nos faltan.
La clase de complejidad \(NP\)-difícil consiste de aquellos problemas \(B\) tales que para cualquier problema \(A\) en \(NP\) se cumple que hay una reducción polinomial de \(A\) a \(B\). La clase de complejidad \(NP\)-completo consiste de aquellos problemas en \(NP\)-difícil, que además están en \(NP\).
¿Qué sucedería si algún problema en \(NP\)-difícil lo pudiéramos resolver en tiempo polinomial? Por la observación anterior tendríamos que cualquier problema en \(NP\) podríamos resolverlo en tiempo polinomial. Pasaría lo mismo si algún problema en \(NP\)-completo lo pudiéramos resolver en tiempo polinomial.
El problema P vs. NP#
El primer problema que se demostró que era \(NP\)-completo es el problema SAT, una versión más general del problema lógico que discutimos arriba. Esto lo hicieron Stephen Cook y Leonid Levin. Luego, Richard Karp encontró muchos otros más. De hecho, se dio cuenta de que 21 problemas de fuerte interés para la comunidad computacional eran \(NP\)-completos.
De ahí en adelante se ha demostrado que muchísimos problemas son \(NP\)-completos. Algunos de ellos son muy técnicos, pero también hay otros muy naturales tanto en el contexto matemático, como en el computacional, como en el aplicado. En la siguiente lista se mencionan algunos, comenzando con los tres que vimos anteriormente que están en \(NP\).
Suma de subconjuntos.
Trayectoria hamiltoniana.
3-SAT
Número de clique de una gráfica.
Número cromático de una gráfica.
Problema del agente viajero: el que hemos discutido como el del brazo del robot.
Número de empacamiento.
Encontrar cortes máximos.
En esta lista hay algunos problemas que definimos inicialmente como optimización. Para transformarlos en problema de decisión, agregamos, por ejemplo, un valor \(k\) a la entrada y los transformamos al problema de optimización de saber si hay un objeto cuya función a optimizar es mayor (o menor) que \(k\).
Muchos de los problemas \(NP\)-completos son fundamentales en varias áreas. Miles de personas, incluidos los expertos de dichas áreas, se los han encontrado y han intentado resolverlos en tiempo polinomial. Hasta ahora, nadie ha logrado resolver ninguno de ellos en tiempo polinomial. Ni nadie ha demostrado que para alguno de ellos esto sea imposible. Como son problemas \(NP\)-completos, basta con que uno de ellos esté en \(P\) para que todos lo estén. Si esto llegara a suceder, las clases de complejidad \(P\) y \(NP\) serían la misma y por lo tanto en un sentido muy amplio sería igual responder problemas que verificar su solución.
Por todas estas razones, la siguiente es una fundamental en matemáticas y ciencias de la computación.
Problema. ¿Será que \(P=NP\)?
Tarea moral#
Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.
Considera los siguientes problemas. Explica, por lo menos de manera informal, cómo constuirías testigos y verificadores para ver que están en NP:
Dada una gráfica \(G\) y un entero \(k\), decidir si \(G\) se puede colorear propiamente con \(k\) colores.
Dada una gráfica \(G\) con aristas ponderadas y un real \(r\), dedicir si existe una trayectoria de peso menor que \(k\) que pase por todas las aristas.
Dado un conjunto \(X\) de enteros positivos, saber si se puede hacer una partición de \(X\) en conjuntos \(X_1\) y \(X_2\) tal que la suma de los elementos en \(X_1\) sea igual a la suma de los elementos en \(X_2\).
Justifica, por lo menos de manera un poco informal, por qué todos los problemas de la clase \(P\) están en la clase \(NP\).
Para saber más del problema de \(P\) vs. \(NP\), y de otros Problemas del Milenio del Instituto Clay, revisa la lista reproducción relacionada con ello en el canal de Arilin’s Math World.
En la definición de reducción polinomial pedimos que \(\varphi(I)\) sea de tamaño polinomial en \(I\). Explica por lo menos intuitivamente por qué esto es redundante, es decir, por qué el hecho de que la reducción toma tiempo polinomial ya implica esto.
Muestra con cuidado que el problema de encontrar un emparejamiento máximo en una gráfica bipartita tiene una reducción polinomial el problema de encontrar un flujo máximo en una red.