El Problema del Milenio PvsNP: Introducción a la NP-Completitud

FACULTAD DE MATEM´ ATICAS Trabajo fin de Grado Grado en Matem´aticas El Problema del Milenio PvsNP: Introducci´on a la NP-Completitud Realizado por Andr´es Nicol´as Uranga Lim´on Dirigido por Antonio Ram´ırez de Arellano Marrero Departamento Ciencias de la Computaci´on e Inteligencia Artificial Sevilla, Junio de 2023 Agradecimientos Este trabajo no hubiera sido posible sin el cari˜no incondicional de mis padres y hermana, el apoyo de mis compa˜neros y la perseverancia de mi tutor. A todos ellos, mis m´as sinceros agradecimientos. I Resumen La Teor´ıa de la Complejidad Computacional es una rama de las ciencias de la computaci´on que estudia la clasificaci´on de problemas en funci´on de los recursos requeridos para resolverlos (tiempo y espacio). Entre los problemas m´as estudiados en este campo se encuentra uno de los Siete Problemas del Milenio propuestos por la fundaci´on Clay Mathematics Institute de Cambridge, el Problema “Pvs NP”, siendo uno de los m´as importantes no s´olo en este ´ambito, sino dentro de las matem´aticas en general. En este Trabajo Fin de Grado se introducir´a al problema y uno de los grandes caminos para atacarlo: la Teor´ıa de la NP -completitud, exponiendo sus problemas cl´asicos y m´etodos asociados. Para concluir, se har´a una reflexi´on de c´omo aplicar dicha teor´ıa y la implicaciones en la sociedad de sus posibles respuestas. III Abstract Computational Complexity Theory is a branch of computer science that studies the problems classification according to the resources required to solve them (time and space). Among the main problems studied in this field we find one of the Seven Millennium Problems proposed by the Clay Mathematics Institute of Cambridge, the Problem “Pvs NP”, being one of the most important not only in this field, but also in mathematics in general. In this Final Degree Project we will introduce the problem and one of the main ways to attack it: the NP-completeness theory, exposing its classical problems and associated methods. Finally, a reflection will be made on how to apply this theory and the implications in society of its possible answers. V ´ Indice general ´ Indice general VII ´ Indice de tablas IX ´ Indice de figuras XI Introducci´on 1 1 Preliminares 3 1.1 Introducci´on a la Teor´ıa de la Complejidad Computacional . . . . . . . . . . . 3 1.1.1 Problemas de decisi´on, lenguajes y esquemas de codificaci´on . . . . . . . . 3 1.1.2 Lam´aquinadeTuring............................. 6 1.1.3 La clase P................................... 9 1.1.4 La clase NP ................................... 10 1.2 Definiciones de teor´ıa de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3 Forma Normal Conjuntiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4 Notaci´on O...................................... 15 2 Introducci´on a la NP-completitud 17 2.1 La relaci´on entre PyNP .............................. 17 2.2 Reducciones polinomiales y NP-Completitud................... 18 2.3 TeoremadeCook .................................. 21 2.4 Problemas NP-completos cl´asicos . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4.1 3-SATISFIABILITY.............................. 26 2.4.2 3-Dimensional Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4.3 Vertex Cover y Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.4.4 CicloHamiltoniano............................... 36 2.4.5 Partici´on .................................... 39 2.5 Problemas adicionales: M´etodos para probar la NP-completitud de un problema 42 2.5.1 Restricci´on ................................... 42 2.5.2 Reemplazamiento Local . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.5.3 Dise˜no de componentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3 Aplicaciones de la NP-completitud y fronteras entre las clase PyNP 47 3.1 An´alisis de subproblemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2 2SAT est´a en P................................... 53 3.3 Implicaciones de P=NP: Existencia de problemas NP-intermedios . . . . . . . 55 VII 2´ Indice de figuras El problema “Pvs NP” consiste en determinar si los problemas de los que sabiendo una soluci´on, es posible verificar, en tiempo polinomial, si esta es o no factible (clase NP), se diferencian de aquellos cuya soluci´on puede ser hallada en tiempo polinomial (clase P). En este trabajo se definir´a formalmente qu´e es la clase Py la clase NP. Posteriormente, se expondr´a uno de los m´etodos y clases que se usan para probar que P=NP, la teor´ıa de la NP-completitud y las reducciones. El objetivo, es que el lector, una vez concluido el texto, entienda el problema “Pvs NP” y aprenda trabajar con algunas herramientas b´asicas que se emplean para atacar este problema. La estructura del proyecto est´a dividida en cuatro cap´ıtulos. En el primero de ellos, se presentan las m´aquinas de Turing, el modelo computacional utilizado y se definen las clases PyNP. En el segundo, ya se definen la NP-completitud y las reducciones polinomiales. Adem´as, aparece SAT como primer problema NP-completo, y como base del resto de las reducciones polinomiales ejecutadas para probar la NP-completitud de algunos problemas cl´asicos. En el tercero, se muestra c´omo la NP-completitud se aplica para buscar una frontera entre Py los problemas NP-completos. Finalmente, en el cap´ıtulo cuatro, se resumir´an las conclusiones del autor y se reflexionar´a sobre perspectivas futuras sobre el estudio del problema “Pvs NP”. CAP´ ITULO 1 Preliminares El presente cap´ıtulo otorga las herramientas necesarias para comprender qu´e es la clase Py la clase NP. Para ello ser´a conveniente familiarizarse con los lenguajes y los problemas de decisi´on. Tambi´en, ser´a preciso para formalizar la teor´ıa un modelo de computaci´on convencional: Las m´aquinas de Turing. Para concluir el cap´ıtulo, debido a que la gran mayor´ıa de los problemas expuestos en el segundo y tercer cap´ıtulos pertenecen a la teor´ıa de grafos, se ha considerado oportuno a˜nadir una secci´on donde se puedan consultar aspectos generales de los mismos. Seguidamente aparecer´a una breve definici´on de Forma normal Conjuntiva , y se introducir´a la notaci´on Ode Landau. 1.1– Introducci´on a la Teor´ıa de la Complejidad Computacional En esta secci´on, se procede a introducir el tema de la complejidad computacional. Se comienza con la definici´on de los problemas de decisi´on, problemas que plantean una pregunta que se responde con “s´ı” o “no”, as´ı como las herramientas necesarias para su tratamiento. Posteriormente, se realiza una revisi´on exhaustiva del modelo computacional que se emplear´a para abordar formalmente el estudio: las m´aquinas de Turing. Finalmente, se presentan las clases de complejidad PyNP. La nomenclatura de est´a secci´on est´a basada en los libros [1,7], los cuales se recomiendan para m´as informaci´on. 1.1.1. Problemas de decisi´on, lenguajes y esquemas de codificaci´on Problemas de decisi´on Por conveniencia la teor´ıa de la NP-completitud est´a dise˜nada para ser aplicada a problemas de decisi´on. En teor´ıa de la complejidad, un problema de decisi´on es un tipo de problema computacional que estudia si una instancia de un problema dado satisface o no una cierta propiedad o criterio espec´ıfico. Formalmente, un problema de decisi´on DΠse puede definir como una funci´on que toma como entrada una instancia o conjunto de datos de un problema y devuelve una respuesta 3 41. Preliminares afirmativa o negativa (por ejemplo, “s´ı” o “no”) seg´un si la instancia satisface o no la propiedad en cuesti´on. Por ejemplo, el problema de decisi´on “¿Existe un camino de longitud kentre los nodos uyven un grafo G?” devuelve una respuesta afirmativa si existe un camino de longitud kentre uyven G, y una respuesta negativa si no existe tal camino. Otro problema de decisi´on relevante es el Problema del vendedor ambulante. Este consiste en dados un conjunto de ciudades, una distancia entre las ciudades y un entero B. ¿Existe un camino que pase por todas las ciudades y llegue a la ciudad de partida de manera que la longitud del trayecto es menor o igual que B? Formalmente, se escribe: Problema del vendedor ambulante Instancia: Sean C={c1, c2, . . . , cm}de ciudades, duna distancia cumpliendo d(ci, cj)∈Npara todo par de ciudades ci, cj∈CyB∈N. Pregunta: ¿Existe un camino por todas las ciudades de Cde longitud menor o igual que B, es decir, un ordenaci´on < cπ(1), cπ(2), . . . , cπ(m)>de Ctal que m−1 X i=1 d(cπ(i), cπ(i+1))+d(cπ(m), cπ(1))≤B? La teor´ıa de la complejidad se enfoca en los problemas de decisi´on porque pueden ser formulados de manera clara y precisa en t´erminos de una pregunta que se puede responder con “s´ı” o “no”. Adem´as, muchos otros tipos de problemas pueden reducirse en problemas de decisi´on. Por ejemplo, si se quiere encontrar la ruta m´as corta entre dos puntos en un mapa, se puede reformular la pregunta como “¿existe una ruta de longitud menor o igual aXque conecte los dos puntos?”. El enfoque en problemas de decisi´on permite una mayor claridad y precisi´on en la definici´on de la complejidad computacional. En particular, se pueden establecer criterios objetivos para medir la dificultad de un problema, como el n´umero de pasos computacionales necesarios para resolverlo en el peor de los casos. Esto permite clasificar los problemas en diferentes clases de complejidad, seg´un su dificultad relativa y los recursos computacionales requeridos para resolverlos. En resumen, la teor´ıa de la complejidad se enfoca en problemas de decisi´on porque son una forma clara y precisa de definir problemas y porque permiten una medici´on objetiva de la dificultad de los mismos. Lenguajes El concepto de lenguaje surge de esa necesidad de un instrumento matem´atico que nos permita estudiar la complejidad de un problema de decisi´on.[7] Un lenguaje es un conjunto de cadenas finitas formadas por s´ımbolos de un alfabeto dado. Si Σ es un conjunto finito de s´ımbolos, entonces Σ∗es el conjunto de todas las posibles cadenas finitas formadas por s´ımbolos de Σ. Si Les un subconjunto de Σ∗, entonces Les un lenguaje sobre el alfabeto Σ. A la palabra que no tiene ning´un s´ımbolo se le conoce como palabra vac´ıa y se denota por ϵ. Por ejemplo, si Σ = {0,1}, entonces Σ∗est´a compuesto por la cadena vac´ıa ϵy todas las cadenas finitas que se pueden formar con los s´ımbolos 0 y 1. Un ejemplo de un lenguaje sobre Σ ser´ıa L={01,111,000,10}. 1.1. Introducci´on a la Teor´ıa de la Complejidad Computacional 5 Esquema de codificaci´on de un lenguaje La correspondencia entre los problemas de decisi´on y los lenguajes se lleva a cabo mediante los esquemas de codificaci´on. Un esquema epara un problema de decisi´on Π proporciona una descripci´on de cada instancia de Π mediante una palabra adecuada sobre cierto alfabeto Σ. Por lo tanto, el problema Π y su esquema de codificado eparticionan Σ∗en tres clases: aquellas que no son codificaciones de instancias de Π, aquellas que codifica instancias con respuesta “no” y aquellas que codifican instancias con respuesta “si”. Esta ´ultima clase constituye el lenguaje asociado a el problema de codificaci´on Π por medio del esquema de codificaci´on e: L[Π, e] = x∈Σ∗:Σ es el alfabeto usado por e, y xes la codificaci´on por ede una instancia con respuesta positiva  La teor´ıa ser´a aplicada a problemas de decisi´on utilizando que si un resultado se verifica para el lenguaje L[Π, e], entonces tambi´en se tiene para el problema Π codificado por el esquema e. Como el objetivo ser´a estudiar la complejidad, resulta ´util asociar a cada problema de decisi´on una funci´on Tama˜no :DΠ→Nque no dependa del esquema de codificaci´on y que est´e polinomialmente relacionada con las longitudes de los datos de entrada. La expresi´on polinomialmente relacionada se refiere a que para cualquier esquema de codificaci´on ede Π, existan dos polinomios pyp′tal que si I∈DΠyxes una cadena codificando a I mediante e, entonces Tama˜no(I)≤p(|x|) y |x| ≤ p′(Tama˜no(I)), donde |x|es la longitud de x. Remarcar, tambi´en, que el hecho de que la funci´on sea polinomial es importante, pues si fuera de otro tipo (exponencial, por ejemplo) habr´ıa un conflicto con la definici´on de complejidad. Debido a la definici´on dada de esquemas de codificaci´on, no hay unicidad en la codificaci´on, es decir, para un mismo problema de decisi´on se pueden encontrar distintos esquemas de codificaci´on v´alidos. Sin embargo durante el resto trabajo se usar´a un esquema concre- to, el que se da en el pr´oximo p´arrafo. La principal caracter´ıstica que debe tener uno de estos esquemas es que debe ser conciso y debe poder descodificarse. El siguiente ejemplo de esquema de codificaci´on forma parte de aquellos que llamamos razonables. La codificaci´on consistir´a en identificar instancias con cadenas del alfabeto Ψ = {0,1,−,[,],(,), , }. Las cadenas se forman de la siguiente forma: 1. Si kes un n´umero entero se le asocia su representaci´on en binario (precedida de un signo “-” si kes negativo). 2. Si xes una cadena que representa a k, entonces la cadena [x] se usa como nombre (por ejemplo, un v´ertice en un grafo o una ciudad en el problema del vendedor). 3. Si x1, x2, . . . , xmes una cadena representado los objetos X1, X2, . . . , Xm, entonces (x1, x2, . . . , xm) es la cadena que codifica la sucesi´on ⟨X1, X2, . . . , Xm⟩. Debido a este m´etodo, la codificaci´on de una instancia de un problema queda determinada por la codificaci´on de sus objetos al usar la regla (3). Por lo tanto, ´unicamente es necesario especificar como se construye la representaci´on de cada objeto. Los objetos que aparecer´an en las instancias son: enteros, “elementos sin estructura”, sucesiones, conjuntos, grafos, aplicaciones finitas y n´umeros racionales. 61. Preliminares •Las reglas (1) y (3) dan la representaci´on de los enteros y las sucesiones. •A los elementos sin estructura se le asignar´an un nombre usando la regla (2). •Un conjunto de objetos se representar´a ordenando sus elementos en una sucesi´on ⟨X1, X2, . . . , Xm⟩y tomando la estructura de cadena correspondiente a esa sucesi´on. •Un grafo de v´ertices Vy aristas Ese representar´a con la cadena (x, y), donde xes la cadena que representa Veyes la cadena que representa el conjunto E. Una aplicaci´on finita f:{U1, U2, . . . , Um} → Wse representar´a con la cadena ((x1, y1),(x2, y2),...,(xm, ym)) donde xicodifica Uiyyi,f(Ui) para 1 ≤i≤m. •Un n´umero racional q=a bse representar´a con la cadena (x, y) donde xes la cadena asociada a ayy, a b. Esto constituye un ejemplo de esquema de codificaci´on. Aunque no ser´a relevante a lo largo del trabajo, es conveniente que el lector tenga conocimiento de al menos uno de estos esquemas. Como ya se ha dicho, muchos esquemas de codificaci´on son v´alidos para un mismo problema de decisi´on, siempre y cuando cumplan las dos condiciones de concisi´on y decodificaci´on. 1.1.2. La m´aquina de Turing En 1936, el matem´atico brit´anico Alan Turing introdujo por primera vez el concepto de m´aquina de Turing [20]. Su objetivo era describir una m´aquina que pudiera realizar cualquier c´alculo expresado por medio de un algoritmo. Aunque la m´aquina de Turing no sea un modelo pr´actico para la computaci´on en m´aquinas reales, debido a su sencillez y su potencia, ha proporcionado una base te´orica robusta para el desarrollo de las ciencias de la computaci´on y de la Teor´ıa de la Complejidad Computacional. La descripci´on de la m´aquina de Turing que aparece a continuaci´on y en los siguientes apartados aparece de forma m´as detallada en [1]. Tambi´en se inspira en [10]. La idea detr´as de una m´aquina de Turing es la de una cinta infinita dividida en recuadros en los cuales hay escritos s´ımbolos. Una cabeza lectora, que se puede mover a derecha o izquierda, se encarga de leer, borrar o escribir en los recuadros de acuerdo a una serie de reglas. Figura 1.1: Ejemplo de M´aquina de Turing sobre el alfabeto Σ = {0,1}. 1.1. Introducci´on a la Teor´ıa de la Complejidad Computacional 7 La cinta no es m´as que una l´ınea infinita dividida en celdas en las que se escriben s´ımbolos de un conjunto finito Γ llamado alfabeto de la m´aquina. Esta est´a equipada con una cabeza lectora que se encarga de leer, borrar o escribir s´ımbolos en la cinta. La computaci´on de la m´aquina se realiza en pasos de tiempo discretos, y la cabeza se mueve a izquierda o derecha en cada paso. Consultar figura 1.1. La m´aquina tiene tambi´en un conjunto finito de estados denotado por Q, en cada paso la m´aquina se encuentra en un ´unico estado de Q. Este estado determina cu´al ser´a la pr´oxima computaci´on de la m´aquina que consiste en: 1. Leer el s´ımbolo que est´a en la celda de encima de la cabeza. 2. Cambiar el s´ımbolo por otro s´ımbolo (puede ser el mismo). 3. Pasar a otro estado de Q. 4. Mover la cabeza a la casilla de la izquierda, la de la derecha o permanecer en la misma celda. La m´aquina de Turing puede ser interpretada como una computadora moderna simplificada cuya cinta corresponde con la memoria de la computadora y su funci´on de transici´on es la CPU (unidad central de procesamiento). Sin embargo, nuestro enfoque ser´a el de describir algoritmos de manera simple y matem´atica. En ocasiones, para facilitar la labor, conviene usar m´aquinas con m´as de una cinta. Sin embargo, se puede demostrar que son polinomialmente equivalentes a las de una cinta. Como la funci´on de las m´aquinas de Turing en este trabajo es formalizar el modelo de computaci´on, no se definir´an este tipo de m´aquinas. El lector interesado puede encontrar m´as informaci´on en el primer cap´ıtulo de [1]. M´aquina de Turing determinista A continuaci´on, se da una descripci´on formal de la m´aquina de Turing determinista: Una m´aquina de Turing determinista (MTD)Mes una tupla (Γ,Q,δ) donde : •Γ es un conjunto finito de s´ımbolos que puedes aparecer en la cinta de M. Γ contiene un alfabeto de entrada con los s´ımbolos que se le introducen a la m´aquina, llamado Σ. Asumimos que Γ contiene el s´ımbolo □que designa el blanco, y ▷que designa la celda por la que empezamos a leer. Se cumple que ▷, □∈Γ−Σ • Q son lo posibles estados en los que se puede encontrar M.Qcontiene tres estados especiales, q0es el estado inicial, qYestado de aceptaci´on y qNestado de rechazo, cumpliendo qY=qN. •δ:Q−{qY, qN}×Γ→ Q×Γ×{L, R, N}es la funci´on de transici´on (Lindica que la cabeza se mueva a la izquierda; R, a la derecha; y Nque se quede en la misma celda). A δle exigimos que si δ(q, ▷) = (p, σ, D) entonces σ=▷yD=R. La MTD M computa como sigue: Inicialmente, Mrecibe como entrada una palabra w=w1w2. . . wn∈Σ∗precedido de ▷, donde la cabeza empieza a leer, el resto de la cinta esta rellena con blancos. Una vez Mempieza, la computaci´on sigue las reglas descritas por la funci´on de transici´on δ. La computaci´on termina si se alcanza qYoqN, de lo contrario la m´aquina no para. 81. Preliminares Mientras Mrealiza su computaci´on, ocurren ciertos cambios en los estados, el contenido de la cinta y la posici´on actual de la cabeza lectora. A una asignaci´on de estos tres elementos la llamamos configuraci´on de la MTD. Sean Muna MTD dada por (Γ,Q,δ), un estado qy dos cadenas u, v ∈Σ∗, se denota como d= (q, u, v) a la configuraci´on donde el estado actual es q, el contenido de la cinta es uv y la cabeza se encuentra en el primer s´ımbolo de v(si w=ϵ, la cabeza lee □). Figura 1.2: MTD con configuraci´on d= (q3,01,1010). Configuraciones Ahora se formalizar´a la computaci´on de una MTD. Se dice que la configuraci´on d′es sucesora de dsi Mpuede ir de dad′en un ´unico paso. Formalmente, dyd′configuraciones tales que d= (q, v, sw) con s∈Γ, q =qYyq=qN. Se dice que d′= (q′, v′, w′) es la sucesora de drespecto de M,d⊢Md′, cuando: •Si δ(q, s) = (q′, t, N), entonces se indica que, estando en el estado qy leyendo el s´ımbolo s, se realiza una transici´on hacia el estado q′, donde se cambia el s´ımbolo s por ty se mantiene en la misma posici´on en la cinta. En este caso, se establece que el contenido de la cinta no cambia antes ni despu´es de la transici´on, es decir, v′=v yw′=tw. •Si δ(q, s)=(q′, t, R), entonces se indica que, estando en el estado qy leyendo el s´ımbolo s, se realiza una transici´on hacia el estado q′, donde se cambia el s´ımbolo spor ty se mueve hacia la derecha en la cinta. En este caso, se establece que el contenido de la cinta despu´es de la transici´on es igual al contenido original de la cinta, excepto que el s´ımbolo sha sido reemplazado por t, es decir, v′=vt yw′=w. •Si δ(q, s)=(q′, t, L), entonces se indica que, cuando se alcanza el estado qy se lee el s´ımbolo s, se realiza una transici´on hacia el estado q′, donde se cambia el s´ımbolo spor ty se mueve hacia la izquierda en la cinta. En este caso, se establece que el contenido de la cinta despu´es de la transici´on se obtiene al insertar el s´ımbolo ten la posici´on actual. Es decir, si era v=ur (donde res cualquier s´ımbolo de Γ), entonces el contenido de la cinta despu´es de la transici´on se obtiene al poner ten la posici´on actual, seguido por wy precedido por ur, lo que se puede escribir como v′=uy w′=rtw. Si d= (q, v, ϵ), entonces d⊢Md′si (q, w, □)⊢Md′. 1.1. Introducci´on a la Teor´ıa de la Complejidad Computacional 9 Una configuraci´on de M,d= (q, v, sw) es de parada si q=qY, en cuyo caso ser´a una configuraci´on de aceptaci´on, o q=qN, que ser´a una configuraci´on de rechazo. Para acabar este apartado se muestra un ejemplo de MTD que dado un n´umero escrito en binario determina si este es par en la tabla 1.1. En esta m´aquina de Turing, si el n´umero binario es par, la m´aquina llegar´a al estado de aceptaci´on qY, si no se llegar´a a un estado de rechazo qN. Estado actual S´ımbolo actual Nuevo s´ımbolo Movimiento Nuevo estado q00 0 R q0 q01 1 R q0 q0□ □ Lq1 q10 0 L qY q11 1 L qN q1□ □ RqN Tabla 1.1: MTD que determina si un n´umero binario es par. Computaci´on Una vez explicado lo que es una configuraci´on, se procede a definir que es una computaci´on de M. Sea Muna MTD, fijado x∈Σ se define la computaci´on de Msobre xcomo la sucesi´on (posiblemente infinita) de configuraciones de M, d0, d1, d2, . . . tal que: •d0= (q0, ▷, x) •Para cada i, si di= (q, v, w) no es de parada, di+1 est´a definida y di⊢Mdi+1 Lenguaje de una m´aquina de Turing Se dice que una m´aquina de Turing Macepta una cadena xsi la computaci´on de M sobre xacaba en un estado de aceptaci´on. El conjunto de cadenas que Macepta es el lenguaje de Mo el lenguaje reconocido por M, denotado por LM. Hay que destacar que la definici´on de reconocimiento de lenguaje no requiere que M pare sobre todas las cadenas de Σ∗, solo para las de LM. Si x∈Σ∗−LM, entonces la computaci´on de Msobre xpuede que pare en el estado qNo que sea infinita. La resoluci´on de problemas de reconocimiento de lenguajes y de problemas de decisi´on est´a ligada. Decimos que una MTD M resuelve el problema de decisi´on Π bajo el esquema de codificaci´on esi Mpara sobre todas las cadenas del alfabeto de entrada y LM=L[Π, e]. 1.1.3. La clase P En esta secci´on se comienza a tratar el concepto de “complejidad en tiempo” definiendo la clase P. La clase de complejidad Pes la clase de problemas de decisi´on que pueden ser resueltos por una m´aquina de Turing determinista en tiempo polin´omico. Esto significa que existe un algoritmo que puede resolver el problema en un tiempo que crece como una funci´on polin´omica del tama˜no de la entrada. El tiempo empleado en una computaci´on de una MTD M es el n´umero de pasos que se ejecutan hasta que se alcanza un estado de parada. Para una MT D que para sobre todas 10 1. Preliminares sus posibles entradas x∈Σ, su funci´on de complejidad de tiempo TM:N→Nest´a dada por: TM(n) = max m∈N:Σ existe x∈Σ∗, con |x|=ntal que la computaci´on de Mcon entrada xtarda tiempo m Un programa Mse conoce como MTD que tarda tiempo polinomial si existe un polinomio ptal que para todo n∈N,TM(n)≤p(n). La clase de lenguajes Pse define como sigue: P={L⊆Σ∗: existe una MT D que tarda tiempo polinomial Mcon L=LM} Se dice que el problema de decisi´on Π pertenece a Pcon el esquema de codificaci´on e si L[Π, e]∈P. Es decir, si hay una MTD que resuelve en tiempo polinomial el problema Π codificado por e. Sin embargo, para simplificar la notaci´on debido a la existencia de varios esquemas de codificaci´on v´alidos para el mismo problema de decisi´on Π, se dice simplemente que Π pertenece a P. La clase de complejidad Pes una de las clases m´as importantes en teor´ıa de la computaci´on y es considerada una medida de la eficiencia de los algoritmos. Muchos problemas pr´acticos pueden ser resueltos eficientemente en tiempo polin´omico, lo que significa que son tratables en t´erminos de complejidad computacional. 1.1.4. La clase NP En esta secci´on se exponen las herramientas necesarias para entender la segunda clase importante de lenguajes que se estudiar´a en el trabajo, la clase NP. En el desarrollo de la secci´on tomar´an un papel relevante los algoritmos no deterministas y las M´aquinas de Turing no deterministas. Estos al poder tomar distintos valores para un mismo dato de entrada poseen m´as potencia y eficacia que los algoritmos deterministas, lo cual, en principio, permite resolver en tiempo polinomial nuevos problemas. Algoritmos no deterministas Intuitivamente se dice que NP est´a relacionado con los algoritmos no deterministas. Un algoritmo no determinista es aquel que puede producir resultados diferentes cada vez que se ejecuta, incluso con la misma entrada. A diferencia de los algoritmos deterministas, que producen un ´unico resultado cada vez que se ejecutan con la misma entrada, los algoritmos no deterministas no tienen una computaci´on preestableciada para un mismo dato de entrada sino que a medida que avanza el algoritmo se pueden dar distintas opciones. Los algoritmos no deterministas suelen utilizar t´ecnicas como la aleatoriedad o la b´usqueda heur´ıstica para explorar diferentes caminos y posibilidades para resolver un problema. Por ejemplo, el algoritmo no determinista de b´usqueda en profundidad puede explorar diferentes caminos en un grafo para encontrar un objetivo, pero es posible que elija diferentes caminos cada vez que se ejecuta. La figura 1.3 representa los distintos caminos que puede seguir un algoritmo no determinista. Para entender un algoritmo no determinista se establecen dos fases, la primera etapa es la fase aleatoria o fase no determinista y la segunda la fase de comprobaci´on o fase determinista. Dada Iuna instancia de un problema, la primera etapa genera una posible estructura S. Posteriormente, IySse utilizan como entradas para la fase de comprobaci´on, 1.1. Introducci´on a la Teor´ıa de la Complejidad Computacional 11 Figura 1.3: Computaci´on no determinista. A medida que la computaci´on avanza se pueden seguir distintos caminos. que procede de manera determinista. En la primera fase se propone una posible soluci´on al problema y en la segunda se comprueba de forma determinista si esta es, efectivamente, una soluci´on. Un algoritmo no determinista resuelve un problema de decisi´on Π si se tienen las siguientes propiedades para todas las instancias I∈DΠ: 1. Si Itiene respuesta “s´ı”, entonces existe una estructura Sque, una vez generada I, te lleva a una respuesta positiva para IySen el estado de comprobaci´on. 2. Si Ino tiene respuesta “s´ı”, entonces no existe una estructura Sque, una vez generada I, te lleva a una respuesta positiva para IySen el estado de comprobaci´on. Se dice que un algoritmo no determinista resuelve el problema de decisi´on Π en “tiempo polinomial” si existe un polinomio ptal que para toda instancia con respuesta positiva hay alguna estructura Sque lleve la comprobaci´on determinista a la respuesta “s´ı” para IySen tiempo p(Tama˜no(I)). Destacar que esto impone una restricci´on a Spues solo se puede usar tiempo polinomial en comprobar la posible respuesta generada. De manera informal la clase NP se define como la clase de los problemas de decisi´on Π que, bajo un esquema de codificaci´on adecuado, pueden ser resueltos por un algoritmo no determinista en tiempo polinomial. El t´ermino “resuelto” debe ser entendido con precauci´on, un“algoritmo no determinista en tiempo polinomial” es b´asicamente un instrumento para definir la noci´on de tiempo polinomial de verificaci´on, en lugar de un m´etodo real para resolver problemas de decisi´on. Ahora, en vez de una ´unica posible computaci´on, puede tener varias diferentes. Hay otro aspecto en el que la soluci´on de un problema de decisi´on por un algoritmo no determinista se diferencia de la de un algoritmo determinista: la ausencia de simetr´ıa entre el “s´ı” y el “no”. Si el problema “¿Dado I,Xes verdadero para I?” puede ser resuelto en tiempo polinomial por un algoritmo determinista, entonces el problema complementario, “¿Dado I,Xes falso para I?”,tambi´en. Esto se debe a que en un algoritmo determinista 18 2. Introducci´on a la NP-completitud comprobaci´on de Aa la respuesta “s´ı” para esa entrada en no m´as de q(n) pasos. Por lo tanto, el n´umero de posibles suposiciones que necesitamos considerar es a lo m´as kq(n), donde k=|Γ|, y como las suposiciones son mas cortas que q(n) se pueden considerar como suposiciones de longitud exactamente q(n) rellenando con blancos si es necesario. Ahora se puede comprobar de forma determinista si Atiene una computaci´on aceptaci´on dada una entrada de longitud naplicando la fase de comprobaci´on de A, hasta que pare o haga q(n) pasos, en cada una de las kq(n)suposiciones. Este programa devolver´a la respuesta “s´ı” si llega a una computaci´on de aceptaci´on sin llegar al l´ımite de tiempo y “no”en caso contrario. Esto da un algoritmo determinista para resolver Π. Adem´as, su complejidad es exactamente q(n)kq(n), como se quer´ıa ver. La capacidad de un algoritmo no determinista de comprobar un n´umero exponencial de posibilidades en un tiempo polinomial lleva a pensar que este tipo de algoritmos son m´as potentes que los deterministas. De hecho, para algunos problemas concreto de NP, como el del Vendedor ambulante o el del Isomorfismo de subgrafos entre otros, no se han podido encontrar algoritmos en tiempo polinomial para su resoluci´on. Por estas razones, la finalidad de este trabajo ser´a intentar dar las t´ecnicas que se utilizan actualmente para demostrar que P=NP buscando los problemas m´as “dif´ıciles” de NP. Figura 2.1: Posible imagen de NP. 2.2– Reducciones polinomiales y NP-Completitud Si Pfuera distinto de NP, la distinci´on entre PyNP −Pes un importante objeto de estudio. Todos los problemas de Ppueden ser resueltos por un algoritmo en tiempo polinomial, mientras que los de NP −Pson irresolubles f´ısicamente con la potencia computacional actual. Por lo tanto, dado un problema de decisi´on Π ∈NP, el objetivo es saber que si pertenece o no a P. 2.2. Reducciones polinomiales y NP-Completitud 19 Naturalmente, hasta que no se pruebe que P=NP, no hay esperanzas de mostrar que ning´un problema particular pertenece a NP −P. Por esta raz´on, la teor´ıa de la NP- completitud se centra en probar resultados m´as d´ebiles del tipo “si P=NP, entonces Π∈NP −P”. Veremos que, aunque este m´etodo puede parecer igual de complicado, existen t´ecnicas que nos permiten dar resultados de forma directa. La clave para llevar a cabo esta tarea son las reducciones polinomiales. Una reducci´on polinomial de un lenguaje L1⊆Σ∗ 1a un lenguaje L2⊆Σ∗ 2es una funci´on f: Σ∗ 1→Σ∗ 2 satisfaciendo la dos siguientes condiciones: 1. Existe un programa de una MTD que computa fen tiempo polinomial. 2. Para todo x∈Σ∗ 1,x∈L1si y solo si f(x)∈L2. Figura 2.2: Esquema de una reducci´on polinomial f,x∈L1si y solo si f(x)∈L2. Si existe tal reducci´on, “L1se reduce a L2” y se denotar´a L1≤pL2, de aqu´ı en adelante. La importancia de las reducciones se ver´a en el siguiente lema: Lema 2.2. Si L1≤pL2yL2∈Pentonces L1∈P. Demostraci´on. Sean Σ1y Σ2los alfabetos de L1yL2respectivamente, f: Σ∗ 1→Σ∗ 2 una reducci´on polinomial de L1en L2,Mfla MTD que computa f, y M2la MTD que reconoce L2. Es posible construir una MTD para L1componiendo Mfcon M2. Para x∈Σ∗ 1, se aplica en primer lugar Mfpara obtener f(x)∈Σ∗ 2. Seguidamente se aplica M2para comprobar si f(x)∈L2. Como L1≤pL2,x∈L1si y solo si f(x)∈L2, hemos construido una MTD que reconoce L1. Que este programa opere en tiempo polinomial se sigue de que MfyM2tambi´en lo hacen. Volviendo a los problemas de decisi´on, si Π1y Π2son dos problemas de decisi´on con esquemas de codificaci´on asociados e1ye2, diremos que Π1≤pΠ2si existe una reducci´on polinomial de L[Π1, e1] en L[Π2, e2]. 20 2. Introducci´on a la NP-completitud Figura 2.3: Obtenci´on de un algoritmo para L1a partir de una reducci´on y un algoritmo polinomial para L2. Uno de los hechos por lo que la “reducibilidad polinomial” es importante es debido a que cumple la propiedad transitiva, la cual es demostrada en el siguiente lema. Lema 2.3. Si L1≤pL2yL2≤pL3, entonces L1≤pL3. Demostraci´on. Sean Σ1, Σ2y Σ3los alfabetos de L1,L2yL3respectivamente, sea f1: Σ∗ 1→Σ∗ 2una reducci´on polinomial de L1en L2, y f2: Σ∗ 2→Σ∗ 3una reducci´on polinomial de L2en L3. Entonces la funci´on f: Σ∗ 1→Σ∗ 3definida como f(x) = f2(f1(x)) para todo x∈Σ∗ 1es la transformaci´on de L1en L3buscada. Esto es as´ı pues la composici´on de dos funciones que pueden ser computadas en tiempo polinomial tambi´en puede ser computada en tiempo polinomial; y porque (x∈L1⇐⇒ f1(x)∈L2)∧(f1(x)∈L2⇐⇒ f2(f1(x)) = f(x)∈L3) Luego x∈L1si y solo si f(x)∈L3 Se dir´a que L1yL2son polinomialmente equivalentes si se cumple L1≤pL2yL2≤pL1. El lema 2.3 nos prueba que ≤pnos da una relaci´on de orden leg´ıtima en la clase de los lenguajes. De hecho, la clase Pforma la menor clase de equivalencia bajo este orden parcial, pudiendo ser vista como los lenguaje m´as “f´aciles”. La clase de los problemas NP-completos forma otra clase de equivalencia, destacada por contener los problemas m´as dif´ıciles de NP. Formalmente, un lenguaje Lse define como NP-duro si, para todo lenguaje L′∈NP, se tiene que L′≤pL. Si adem´as, L∈NP, entonces se dir´a que Les NP-completo. Un problema de decisi´on Π es NP-completo si Π ∈NP y, para todos los problemas de decisi´on Π′se tiene que Π′≤pΠ. Es importante que el problema cumpla ambas condiciones, de hecho existen problemas que son NP-duros y no pertenecen a NP como el problema de la Parada, que no es computable por ninguna m´aquina de Turing, pero s´ı es NP-duro1. El lema 2.3 sugiere que los problemas NP-completos se identifican con los m´as dif´ıciles de NP. S´ı alg´un problema NP-completo puede ser resuelto en tiempo polinomial, entonces todos los dem´as problemas de NP, tambi´en. Si alg´un problema de NP es intratable, este tendr´a que ser un problema NP-completo. Un problema Π NP-completo cumple la propiedad que busc´abamos: “si P=NP, entonces Π ∈NP −P”. Exactamente, Π ∈Psi y solo si P=NP. Asumiendo que P=NP, la figura 2.4 esquematiza el “mundo NP ”. Como se observa, en NP −Phay tanto problemas NP-completos como otro que no est´an en P. 1Una prueba de esto se puede consultar en [1]. 2.3. Teorema de Cook 21 Figura 2.4: Posible imagen de NP, a˜nadiendo los problemas NP-completos. El inter´es del trabajo es el estudio de los problemas NP-completos. Probar que un problema es NP-completo puede ser un poco exigente: uno debe probar que todo problema de NP se reduce a el posible problema NP-completo con el que se est´a trabajando. El siguiente lema simplificar´a la tarea proporcionando una t´ecnica directas para ello. Lema 2.4. Si L1yL2pertenecen a NP,L1es NP-completo, y L1≤pL2, entonces L2 es NP-completo. Demostraci´on. Si L1yL2pertenecen a NP,L1es NP-completo, y L1≤pL2, entonces L2es NP-completo. Como L2∈NP , falta ver que, para todo L′∈NP,L′≤pL2. Sea L′∈NP. Como L1es NP -completo, L′≤pL1. Aplicando la transitividad se tiene el resultado. Volviendo al mundo de los problemas de decisi´on, este lema da esa manera directa de probar que un problema es NP-completo, una vez que se haya encontrado un primer problema NP-completo. Para probar que Π es NP -completo, solo es necesario mostrar que: 1. Π ∈NP, y 2. un problema NP-completo conocido Π′se reduce a Π. Antes de poder usar ese enfoque, ser´a preciso encontrar ese primer problema NP- completo. Dicho problema ser´a tratado en la pr´oxima secci´on. 2.3– Teorema de Cook El problema de decisi´on que tiene el honor de ser el primer NP-completo es el problema de l´ogica boolena “Satisfiability” (SAT abreviado). En esta secci´on se desarrollar´an los t´erminos necesarios para describirlo, as´ı como la prueba de que este problema es, efectivamente, NP-completo. El problema SAT se plantea como sigue: Satisfiability Instancia: Sean Uun conjunto de variables booleanas y Cun conjunto de cl´ausulas sobre U. Pregunta: ¿Existe una asignaci´on de verdad satisfactible para C? 22 2. Introducci´on a la NP-completitud Una vez definido el problema SAT, vamos a enunciar y probar el teorema de Cook. La versi´on que aqu´ı se expone fue la que Cook dio en su art´ıculo “The Complexity of Theorem Proving Procedures” en 1971 y se extrae del libro [7]. Este teorema fue probado independientemente por Leonid Levin aproximadamente en la misma fecha, por lo que tambi´en se conoce como “Teorema de Cook-Levin”. Teorema 2.5. Satisfiability es NP-completo. Demostraci´on. Sean U={u1, u2, . . . , um}un conjunto finito de variables booleanas y C una colecci´on de cl´ausulas. En primer lugar, ha de probarse que SAT pertenece a la clase NP. Para ello damos un algoritmo 1 no determinista que resuelve el problema: Algoritmo 1 SAT 1: Entrada: Cuna colecci´on de cl´ausulas sobre U={u1, . . . , un} 2: σ← ∅ 3: Fase no determinista 4: para i←1, n hacer 5: Elegir e1, e2 6: e1:σ←σ∪{(ui, T)} 7: e2:σ←σ∪{(ui, F)} 8: Fase determinista 9: Comprobar si σes una asignaci´on de verdad satisfactoria para C 10: si σes una asignaci´on de verdad satisfactoria para Centonces 11: devolver s´ı 12: si no 13: devolver no En segundo lugar, volviendo a nivel de los lenguajes, SAT est´a representado por el lenguaje LSAT =L[SAT, e] para alg´un esquema de codificaci´on e. Debido a que hay infinitos lenguajes en NP no es posible dar una reducci´on para cada uno de ellos. Sin embargo, cada uno de estos lenguajes est´an descritos por una MTND polinomial. Este hecho permite trabajar con una MTND gen´erica My dar una reducci´on general entre LM yLSAT . Por lo tanto, se probar´a tambi´en que LM≤pLSAT para todo L∈NP. Sea Muna MTND polinomial, dada por Γ, Σ, □,Q,q0,qY,qNyδque reconoce el lenguaje L=LM. Con el motivo de facilitar el acceso a las celdas de la cinta, estas aparecer´an enumeradas durante la prueba, siendo el cero el n´umero de la casilla por el que empieza la cabeza lectora, y situando a la derecha los enteros positivos y a la izquierda los negativos en orden creciente. Adem´as, sea p(n) un polinomio sobre los naturales que acota la funci´on complejidad en tiempo TM(n). Para simplificar la prueba, fLser´a descrita como una aplicaci´on entre cadenas sobre Σ e instancias de SAT, en lugar de cadenas para el alfabeto del esquema de codificaci´on de SAT. Por lo tanto, fLcumplir´a que para toda x∈Σ∗,x∈Lsi y solo si fL(x) tiene una asignaci´on de verdad satisfactoria. La clave de la construcci´on de fLes mostrar como los conjuntos de cl´ausulas se usan para comprobar si una entrada xes aceptada por una MTND M, es decir, si x∈L. Si la entrada x∈Σ∗es aceptada por M, entonces existe una computaci´on de aceptaci´on para Msobre xtal que el n´umero de pasos en la computaci´on de aceptaci´on y el n´umero de 2.3. Teorema de Cook 23 s´ımbolos en la cadena supuesta est´an acotados por p(n), donde n=|x|. Dicha computaci´on no puede involucrar ning´un cuadrado de la cinta que no est´e entre el −p(n) y el p(n) + 1, debido a que la cabeza lectora comienza en el cuadrado 1 y se mueve como m´aximo un cuadrado en cada paso. El estado de la computaci´on de comprobaci´on se especifica dando los contenidos de esos cuadrados, el estado en que se encuentra My la posici´on de la cabeza lectora. Asimismo, como no hay m´as de p(n) pasos en la computaci´on de aceptaci´on, a lo m´as se deben considerar p(n) + 1 tiempos distintos. Esto nos permite describir dicha computaci´on usando ´unicamente un n´umero finito de variables y una asignaci´on de verdad asociadas a ellas. Se procede, a continuaci´on, a construir el conjunto de variables Uque resulta al reducir el problema de decisi´on. Identificamos los elementos de Qcomo q0, q1=qY, q2= qN, q3, . . . , qr, con r=|Q|−1; y los elementos de Γ, como s0=□, s1, . . . , sv, y v=|Γ|−1. Se describen tres tipos de variables cada una de las cuales tendr´a una funci´on espec´ıfica detallada en la tabla 2.1 Variable Rango Significado Q[i,k] 0≤i≤p(n) 0 ≤k≤rMest´a en qken tiempo i H[i,j] 0≤i≤p(n) La cabeza lectora escanea −p(n)≤j≤p(n) + 1 la celda jen el instante i S[i,j,k] 0≤i≤p(n) El s´ımbolo skest´a en el −p(n)≤j≤p(n) + 1 cuadrado jen el instante i 0≤k≤v Tabla 2.1: Variables de fLy sus significados. Una computaci´on de Minduce una asignaci´on de verdad de una manera directa, bajo la asunci´on de que si el programa para antes del tiempo p(n), la configuraci´on permanece est´atica en los siguiente pasos, manteniendo el mismo estado de parada, la posici´on de la cabeza y el contenido de la cinta. En el tiempo 0 el contenido de la cinta consiste en la entrada xescrita en las celdas de la 1 a la n, y de la suposici´on w, escrita en las celdas de la −1 a la −|w|, con los dem´as cuadrados blancos. Por otra parte, una asignaci´on de verdad arbitraria para estas variables no tiene por qu´e corresponderse con una computaci´on, mucho menos con una computaci´on de aceptaci´on que contenga los s´ımbolos en un instante concreto, la m´aquina podr´ıa estar simult´aneamente en varios estados y la cabeza lectora podr´ıa estar en cualquier subconjunto de posiciones entre −p(n) y p(n) + 1. La transformaci´on fLconsiste en construir,usando las variables anteriores, una colecci´on de cl´ausulas cumpliendo que una asignaci´on de verdad es satisfactible si y solo si es la asignaci´on de verdad inducida por computaci´on de aceptaci´on para xcuya fase de comprobaci´on tome p(n) o menos pasos y cuya cadena supuesta tenga longitud al menos p(n). En este caso, se tiene: x∈L⇔hay una computaci´on de aceptaci´on de Msobre x ⇔hay una computaci´on de aceptaci´on de Msobre x con p(n) o menos pasos en su fase de comprobaci´on y su cadena supuesta wtiene longitud exactamente p(n) ⇔existe una asignaci´on de verdad satisfactible para la colecci´on de cl´ausulas de fL(x). 24 2. Introducci´on a la NP-completitud Gracias a esto fLsatisfar´a una de las dos condiciones necesarias para ser una reducci´on polinomial (existe una MTD que computa fL). Falta que fLpuede ser computada en tiempo polinomial. Las cl´ausulas en fL(x) se pueden dividir en seis grupos, a cada uno de los cuales se le impondr´a un tipo de restricci´on distinta en su asignaci´on de verdad satisfactible como se ve en la tabla 2.2. Grupo de cl´ausulas Restricci´on impuesta G1En cada tiempo i, M est´a en exactamente un estado G2En cada tiempo i, la cabeza lectora est´a en exactamente una celda G3En cada tiempo i, cada celda contiene exactamente un s´ımbolo de Γ G4En el tiempo 0, la computaci´on est´a en la configuraci´on inicial de la fase de comprobaci´on para la entrada x G5En tiempo p(n), Mha alcanzado qYy aceptado x Para cada tiempo i, 0 ≤i≤p(n), la configuraci´on G6de Men tiempo i+ 1 se sigue de una ´unica funci´on de transici´on δdesde la configuraci´on i Tabla 2.2: Grupos de cl´ausulas y su restricci´on correspondiente. Por la forma en la que se han construido los grupos de cl´ausulas si se cumplen, entonces existe una asignaci´on de verdad satisfactible para x. Por lo tanto, todo lo que hay que mostrar es c´omo pueden se construidos dichos grupos de cl´ausulas. El grupo G1est´a formado por: {Q[i, 0], Q[i, 1], . . . , Q[i, r]}0≤i≤p(n) {Q[i, j], Q[i, j′]}0≤i≤p(n),0≤j < j′≤p(n) Las primeras p(n) + 1 de estas cl´ausulas pueden ser simult´aneamente satisfechas si y solo si para cada tiempo i, M est´a en al menos un estado. Las dem´as (p(n)+1)(r+1)(r/2) cl´ausulas pueden ser simult´aneamente satisfechas si y solo si no existe un tiempo ien el que Mest´e en m´as de un estado. Es decir, G1cumple la misi´on de asegurar que en el tiempo i, M est´e en un ´unico estado. An´alogamente, los grupos G2yG3se encargan, respectivamente, de que la cabeza lectora escanee una ´unica celda y de que cada cuadrado contenga un ´unico s´ımbolo en cada tiempo i. Los grupos G4yG5son m´as simples y est´an formados por cl´ausulas de un literal. En la tabla 2.3. Notar que el n´umero de cl´ausulas en estos grupos y el n´umero de literales en cada cl´ausulas est´an acotados por una funci´on polinomial que depende de n (ya que ryvson constantes determinadas por My, por lo tanto, por L). El ´ultimo grupo de cl´ausulas G6garantiza que cada configuraci´on tenga una ´unica configuraci´on sucesora. A su vez, este grupo est´a dividido en dos subgrupos de cl´ausulas. El primer subgrupo asegura que si la cabeza lectora no est´a escaneando la celda jen el tiempo i, entonces el s´ımbolo en el cuadrado jno cambia entre los tiempos iyi+ 1. Las cl´ausulas de este subgrupo son como siguen: {S[i, j, l], H[i, j], S[i+ 1, j, l]},0≤i < p(n),−p(n)≤j≤p(n)+1,0≤l≤v 2.3. Teorema de Cook 25 Grupo de cl´ausulas Cl´ausulas en el grupo G1{Q[i, 0], Q[i, 1], . . . , Q[i, r]}0≤i≤p(n) {Q[i, j], Q[i, j]′}0≤i≤p(n),0≤j < j′≤p(n) G2{H[i, −p(n)], H[i, −p(n) + 1], . . . , H[i, p(n) + 1]}0≤i≤p(n) {H[i, j], H[i, j]′}0≤i≤p(n),−p(n)≤j < j′≤p(n) G3{S[i, j, 0], S[i, j, 1], . . . , S[i, j, v] 0 ≤i≤p(n), −p(n)≤j≤p(n) {S[i, j, k], S[i, j, k]′}0≤i≤p(n),−p(n)≤j≤p(n), 0≤k < k′≤v G4{Q[0,0]},{H[0,1]},{S[0,0,0]}, {S[0,1, k1]},{S[0,2, k2]},...,{S[0, n, kn]} {S[0, n + 1,0]},{S[0, n + 2,0]},...,{S[0, p(n)+1,0]} donde x=sk1, sk2,...skn G5{Q[p(n),1]} Tabla 2.3: Primeros 5 grupos de Cl´ausulas. Para cualquier tiempo i, celda jy s´ımbolo sl, ocurre que si la cabeza lectora no est´a leyendo la celda jen el tiempo i, y el cuadrado jcontienen el s´ımbolo slen tiempo ipero no en tiempo i+1, entonces la cl´ausula de arriba que depende de i, j ylno ser´a satisfecha. Por lo tanto, las 2(p(n) + 1)2(v+ 1) de este grupo cumplen su funci´on. El subgrupo restante de G6garantiza que el cambio de una configuraci´on a su sucesora se haga de acuerdo a la funci´on de transici´on δde M. Para cada cu´adrupla (i, j, k, l), 0≤i<p(n), −p(n)≤j≤p(n) + 1, 0 ≤k≤ry 0 ≤l≤v, el subgrupo contiene los siguientes tres grupo de cl´ausulas: {H[i, j], Q[i, k], S[i, j, l], H[i+ 1, j + ∆]} {H[i, j], Q[i, k], S[i, j, l], Q[i+ 1, k′]} {H[i, j], Q[i, k], S[i, j, l], S[i+ 1, j, l′]} donde si qk∈Q−{qY, qN}, los valores de ∆, k′ylson tales que δ(qk, sl)=(qk′, sl′,∆) y si qk∈ {qY, qN}, entonces, ∆ = 0, k′=kyl′=l. Estas 6p(n)(p(n) + 1)(r+ 1)(v+ 1) cl´ausulas imponen la restricciones buscadas a la asignaci´on de verdad. Por lo tanto, se ha dado una forma general de construir los grupos de cl´ausulas buscados. Si x∈L, existe una computaci´on de aceptaci´on de Msobre xde tama˜no a los m´as p(n), y dicha computaci´on, dada la interpretaci´on de las variables, impone una asignaci´on de verdad que satisface todas las cl´ausulas en C=S6 i=1 Gi. A la inversa, la construcci´on de Ces tal que cualquier asignaci´on de verdad satisfactible para Cdebe corresponder a una computaci´on de aceptaci´on de Msobre x. Es decir, fL(x) si tiene una asignaci´on de verdad satisfactible si y solo si x∈L. Falta ver que, para un lenguaje Ldado, fL(x) puede ser construida a partir de xen tiempo polinomial en funci´on de n=|x|. Dado L, se toma una MTND M que reconozca Len tiempo polinomial acotado por un polinomio p. Una vez que se tienen My un polinomio pconcretos, es posible construir el conjunto de variables Uy la colecci´on de cl´ausulas C. La acotaci´on polinomial de esta computaci´on se tiene inmediatamente una vez se haya probado que Tama˜no(fL(x)) est´a acotada superiormente por un polinomio en 26 2. Introducci´on a la NP-completitud funci´on de n, donde T ama˜no(I) refleja el tama˜no de la instancia Ibajo un esquema de codificaci´on razonable. Dicha funci´on Tama˜no para el problema SAT puede ser: |U||C|. Ninguna cl´ausula contendr´a mas de 2|U|literales, y el n´umero de s´ımbolos requeridos para describir un literal necesita a˜nadir el factor log(|U|), que esta acotado polinomialmente. Como ryvest´an fijos los a˜naden factores constantes a |U|y a |C|. Se tiene que |U|= O(p(n)2) y |C|=O(p(n)2). De ah´ı que la funci´on Tama˜no(I) = |U||C|=O(p(n)4), es decir, est´a acotada polinomialmente en funci´on de ncomo se buscaba. Por lo tanto, la reducci´on fLse puede computar con un algoritmo en tiempo polinomial que depende de Ly de las elecciones de Myp. Se concluye que para todo L∈NP,fles una reducci´on polinomial de LaLSAT , y, por tanto, SAT es NP-completo. 2.4– Problemas NP -completos cl´asicos La NP-completitud es una de las herramientas fundamentales que se utilizan hoy en d´ıa para estudiar la frontera entre PyNP. En la presente secci´on, se abordar´an algunos de los problemas NP-completos m´as relevantes como pueden ser 3-SATISFIABILITY, 3- DIMENSIONAL MATCHING, VERTEX COVER, HOMILTONIAN CIRCUIT Y PARTITION. En cada apartado se expondr´a el problema y se dar´a una prueba de su NP - completitud siguiendo el esquema de reducciones que se muestra en la figura 2.5. Estas pruebas generalmente se basan en dar una reducci´on adecuada partiendo del Teorema de Cook 2.5 que nos dice que SAT es NP-completo. Gracias a esto se entender´a la importancia de dicho teorema y el por qu´e se ha invertido tiempo y esfuerzo en su demostraci´on. En su mayor´ıa, las pruebas est´an tomadas de [7], aunque tambi´en se han extraido detalles de [12]. Figura 2.5: Secuencia de reducciones de los problemas NP-completos que se trabajar´an. 2.4.1. 3-SATISFIABILITY El problema 3-SATISFIABILITY es una versi´on de SATISFIABILITY donde se le impone a las cl´ausulas la restricci´on de que est´en formadas por exactamente 3 literales. Su estructura hace que sea uno de los problemas m´as usados a la hora de probar resultados de NP-completitud. 2.4. Problemas NP-completos cl´asicos 27 3-SATISFIABILITY (3SAT) Instancia: Sean Uun conjunto de variables booleanas y C={c1, c2, . . . , cm}un conjunto finito de cl´ausulas sobre Ucumpliendo |ci|= 3 para 1 ≤i≤m. Pregunta: ¿Existe una asignaci´on de verdad satisfactible para C? Teorema 2.6. 3SAT es NP-completo. Demostraci´on. Como SAT est´a en NP 3SAT tambi´en los estar´a. Para probar que 3SAT es NP-completo se dar´a una reducci´on de SAT a 3SAT. Sea U={u1, u2, . . . , un}un conjunto finito de variables y C={c1, c2, . . . , cm}un conjunto de cl´ausulas de un problema SAT. El objetivo ser´a construir una colecci´on de cl´ausulas de tres literales C′sobre un conjunto de variables U′cumpliendo que C′es satisfactible si y solo si Clo es. La construcci´on de C′consiste en remplazar cada cl´ausula original cj∈Cpor una colecci´on C′ jde tres literales “equivalente”, que dependen de las variables de Uy algunas variables auxiliares yj∈Ujque solo aparecer´an en las cl´ausulas C′ jy cuya funci´on es que las nuevas cl´ausulas sean equivalentes a las de C. Esto se har´a fijando: U′=U∪   m [ j=1 U′ j   y C′= m [ j=1 C′ j A continuaci´on se mostrar´a como construir C′ jyU′ ja partir de cj. Sea la cl´ausula dada por {z1, z2, . . . , zk}donde zison literales sobre las variables de U. La manera de construir C′ jyU′ jdepender´a de los valores de k. Caso 1. k= 1. U′ j={y1 j, y2 j} C′ j={{z1, y1 j, y2 j},{z1, y1 j, y2 j},{z1, y1 j, y2 j},{z1, y1 j, y2 j}} Caso 2. k= 2. U′ j={{y1 j}}, C′ j={{z1, z2, y1 j},{z1, z2, y1 j} Caso 3. k= 3. U′ j=∅, C′ j={{cj}} Caso 4. k≥4. U′ j={yi j: 1 ≤i≤k−3} C′ j={z1, z2, y1 j}∪n{yi j, zi+2, yi+1 j}: 1 ≤i≤k−4o ∪n{yk−3 j, zk−1, zk}o Para probar que esto es una reducci´on, hay que ver que el conjunto de cl´ausulas C′es satisfactible si y solo si lo es C. Sea t:U→ {T, F}una asignaci´on de verdad satisfactible para C. A continuaci´on se extender´a tat′:U′→ {T, F}, una asignaci´on de verdad satisfactoria para C′. Como las variables de U′−Use particionan en los conjuntos Ujy las variables de U′ jsolo est´an en los conjuntos C′ j, basta probar que tse puede extender a los conjuntos Ujy, en cada caso, hay que comprobar que cada cl´ausula en las C′ jse satisface. Para ello se plantea la siguiente soluci´on distinguiendo cada caso: 34 2. Introducci´on a la NP-completitud Teorema 2.9. Vertex Cover es NP-completo. Demostraci´on. Para ver que Vertex Cover est´a en NP, se que comprueba el algoritmo no determinista que procede de la siguiente manera resuelve VC en tiempo polinomial. En la fase no determinista se genera un conjunto V′de todos los subconjuntos posibles de V de tama˜no menor o igual que K. En la fase determinista, se toma un v´ertice de V′y se eliminan las aristas adyacentes, consiguiendo as´ı G′= (V, E′), donde E′es el conjunto que se obtiene eliminando las aristas adyacentes a v. Se repite este proceso en G′hasta remover Kv´ertices. Si en ese momento E′=∅, entonces existe un recubrimiento de v´ertices de G; en caso contrario V′no es un recubrimiento de v´ertices de G. En segundo lugar, se reducir´a 3SAT a VC. Sea U={u1, u2, . . . , un}un conjunto finito de variables y C={c1, c2, . . . , cm}un conjunto de cl´ausulas de una instancia de 3SAT. Se construir´a, seguidamente, un grafo G= (V, E) y un n´umero natural K≤ |V|tal que G tenga un recubrimiento de v´ertices de tama˜no Ksi y solo si Ces satisfactible. Al igual que en la reducci´on de 3SAT a 3DM, se proceder´a mediante la creaci´on de componentes que dependen de las variables y las cl´ausulas. En este caso se a˜nadir´an, adem´as, aristas que nos permitan conectar las diferentes componentes: •A cada variable ui∈Use le asigna una componente de “establecimiento de verdad” Ti= (Vi, Ei), donde Vi={ui, ui}yEi={{ui, ui}}. Es decir, dos v´ertices unidos por una arista. Cualquier recubrimiento de v´ertices de tener al un v´ertice de Tipara 1 ≤i≤n. Figura 2.10: Componente establecimiento de verdad asociada a la variable ui. •A cada cl´ausula cj∈Cse le asigna una componente de “testeo de sastisfacci´on” Sj= (V′ j, E′ j). Sjest´a compuesta por tres v´ertices y tres aristas en forma de tri´angulo: V′ j={a1[j], a2[j], a3[j]} E′ j={{a1[j], a2[j]},{a1[j], a3[j]},{a2[j], a3[j]}} Figura 2.11: Componente de testeo de satisfacci´on Cjpara la cl´ausula cj. Obs´ervese que para recubrir las aristas de E′ json necesarios al menos 2 v´ertice de V′ j. 2.4. Problemas NP-completos cl´asicos 35 •Por ´ultimo, la parte que se encarga de conectar todas las componentes, el conjunto de aristas de comunicaci´on. Sea cj∈Cuna cl´asula formada por los literales xj, yjy zj. Se construye el siguiente conjunto de aristas: E′′ j={{a1[j], xj},{a2[j], yj},{a3[j], zj}} Estableciendo K=n+ 2myG= (V, E), donde V= n [ i=1 Vi!∪ m [ j=1 V′ j! y E= n [ i=1 Ei!∪ m [ j=1 E′ j!∪ m [ j=1 E′′ j! se concluye la construcci´on de la instancia de VC. En la figura 2.12 se muestra un ejemplo del grafo que se obtiene a partir de U= {u1, u2, u3, u4},C={{u1, u3, u4},{u1, u2, u4}}. Figura 2.12: Instancia de VC resultante de la instancia de 3SAT U={u1, u2, u3, u4}, C={{u1, u3, u4},{u1, u2, u4}}. Aqu´ı K=n+ 2m= 8. La reducci´on puede completarse en tiempo polinomial pues de la construcci´on resultan 2n+3mv´ertices (dos v´ertices por variables y tres por cl´ausula) y n+3m+3maristas (una arista por variable, 3 por cada componente de testeo y 3mpor las aristas de comunicaci´on). Lo ´unico que queda por probar es que Ces satisfactible si y solo si Gtiene un recubrimiento de v´ertices de tama˜no Ko menor. En primer lugar, sea V′⊂Vun recubrimiento de v´ertices de Gcon |V′| ≤ K. Seg´un se se˜nal´o en los p´arrafos anteriores, V′debe contener al menos un v´ertice en cada Tiy al menos dos en cada Sj. Como esto da que V′contiene n+ 2m=Kv´ertices, ocurre que V′ 36 2. Introducci´on a la NP-completitud tiene un v´ertice en cada Tiy dos en cada Sj, exactamente. Este hecho permite considerar la siguiente asignaci´on de verdad: t(ui) = Tsi ui∈V′yt(ui) = Fsi ui∈V′. Para ver que esta asignaci´on de verdad satisface todas las cl´ausulas de cj∈C, se consideran la tres aristas de E′′ j. Solo dos de estas aristas pueden ser recubiertas por v´ertices de V′ j∩V′, as´ı que al menos una de ellas es cubierta por un v´ertice de alg´un Vique pertenezca a V′. Pero esto supone que el literal correspondiente a ese v´ertice, ya sea uioui, de la cl´ausula cj debe ser verdadero bajo la asignaci´on de verdad t, y, por lo tanto, cjse satisface bajo t. Como esto se tiene para todo cj∈C,tes una asignaci´on de verdad satisfactoria. Rec´ıprocamente, sea tuna asignaci´on de verdad satisfactoria para C. El recubrimiento de v´ertices correspondiente V′contiene un ´unico v´ertice de cada Tiy dos de cada Sj. El v´ertice de Tien V′es uisi t(ui) = Tyuisi t(ui) = F. Esto garantiza que al menos una de las tres arista de E′′ jest´e cubierta, pues tsatisface todas las cl´ausulas cj∈C. Por consiguiente, solo necesitamos incluir en V′los v´ertices extremos de Sjde las otras dos aristas de E′′ j, obteniendo as´ı el recubrimiento de v´ertices deseado. Se concluye que 3SAT≤pVC. 2.4.4. Ciclo Hamiltoniano En teor´ıa de grafos se conoce como ciclo Hamiltoniano a aquel que recorre todos los v´ertices del grafo una ´unica vez. Es decir, dado G= (V, E) un grafo existe una sucesi´on ⟨v1, v2, . . . , vn⟩que contenga todos los v´ertices de Vuna ´unica vez y que {vi, vi+1} ∈ E para 1 ≤i<ny{vn, v1} ∈ E. El problema del ciclo Hamiltoniano consiste en dado un grafo, determinar si este contiene o no un ciclo Hamiltoniano: Ciclo Hamiltoniano (CH) Instancia: un grafo G= (V, E). Pregunta: ¿Contiene Gun ciclo Hamiltoniano? Teorema 2.10. Ciclo Hamiltoniano es NP-completo. Demostraci´on. CH es NP pues solo se necesita crear un ciclo de los posibles (fase no determinista) y comprobar si recorre una vez todos los v´ertices del grafo (fase determinista), y recorrer los v´ertices del grafo se completa en tiempo polinomial. A continuaci´on, se reducir´a Vertex Cover a CH. Dada una instancia de VC ,un grafo G= (V, E) y un natural K≤ |V|, se construir´a una instancia G′= (V′, E′) tal que G′ tenga un ciclo Hamiltoniano si y solo si Gtiene un recubrimiento de v´ertices. De nuevo la reducci´on se har´a en t´erminos de componentes. En primer lugar G′constar´a de K“v´ertices selectores”:a1, a2, .., aKcuya funci´on ser´a seleccionar Kde V, los v´ertices de G. En segundo lugar para cada arista de E,G′tendr´a una “componente de testeo de recubrimiento” que garantizar´a que al menos uno de los extremos de la arista est´a entre los Kv´ertices seleccionados. A la arista e={u, v} ∈ Ele corresponder´a la componente que aparece en la figura 2.13. Tendr´a 12 v´ertices, V′ e={(u, e, i),(v, e, i):1≤i≤6} y 14 aristas, E′ e={{(u, e, i),(u, e, i + 1)},{(v, e, i),(v, e, i + 1)}: 1 ≤i≤5} ∪{{(u, e, 3),(v, e, 1)},{(v, e, 3),(u, e, 1)}} ∪{{(u, e, 6),(v, e, 4)},{(v, e, 6),(u, e, 4)}} 2.4. Problemas NP-completos cl´asicos 37 Figura 2.13: Componente de testeo de recubrimiento correspondiente a la arista {u, v}. Los ´unicos v´ertices de la componente de testeo de recubrimiento que aparecer´an en otras aristas son :(u, e, 1),(v, e, 1),(u, e, 6) y (v, e, 6). Esto supone que cualquier ciclo Hamiltoniano de G′debe unirse con E′ een alguna de las tres configuraciones que se muestran en la figura 2.14. Por ejemplo, si el ciclo entra por el v´ertice (u, e, 1) tendr´a que salir por (u, e, 6) y visitar´a los 12 v´ertices o solo los 6 del tipo (u, e, i) con 1 ≤i≤6. El siguiente tipo de aristas que intervienen en la construcci´on tendr´an la funci´on de unir componentes de testeo de recubrimiento con v´ertices selectores. Para cada v´ertice v∈V, sean ev[1], ev[2], . . . , ev[gr(v)], donde gr(v) denota el grado de ven G, es decir, el n´umero de aristas que llegan a v. Todas la componentes de testeo de recubrimiento de estas aristas (que tienen a vcomo extremo) se unen con las siguientes aristas de conexi´on: E′ v={(v, ev[i],6),(v, ev[i+1],1)}: 1 ≤i≤gr(v) Como se observa en la figura 2.15, esto crea un ´unico camino en G′que incluye exactamente los v´ertices (x, y, z) donde x=v. El ´ultimo grupo de aristas de comunicaci´on en G′une el primer y el ´ultimo v´ertice de dichos caminos con los v´ertices selectores a1, a2, .., aK. Estas tienen la siguiente forma: E′′ ={ai,(v, ev[1],1)},{ai,(v, ev[gr(v)],6)}: 1 ≤i≤K, v ∈V El grafo G′= (V′, E′) se completa de la siguiente manera: V′={ai: 1 ≤i≤K}∪[ e∈E V′ e y E′=[ e∈E E′ e∪[ v∈v E′ v∪E′′ 38 2. Introducci´on a la NP-completitud (a) upertenece al recubrimiento de v´ertices pero no lo hace v. (b) uyvpertenece al recubrimiento de v´ertices. (c) vpertenece al recubrimiento de v´ertices pero no lo hace u. Figura 2.14: Tres posibles configuraciones de un ciclo Hamiltoniano en la componente de testeo correspondiente a la arista {u, v}. El n´umero de v´ertices y aristas del nuevo grafo G′depende de los datos de Gde forma polinomial ya que hay K+ 12|E| ≤ |V|+ 12|E|v´ertices y, a lo m´as, 14|E|+|V||E|+ 2|K||V| ≤ 14|E|+|V||E|+ 2|V|2aristas (el sumando |V||E|viene de que para todo v´ertice v∈V,gr(v)≤ |E|). Para concluir, se probar´a que G′tiene un ciclo Hamiltoniano si y solo si Gtiene un recubrimiento de v´ertices de tama˜no Ko menor. Sea ⟨v1, v2, . . . , vn⟩, donde n=|V′|, un ciclo Hamiltoniano de G′. Se considera una parte de este ciclo que empiece en un v´ertice del conjunto {a1, a2, . . . , aK}, acabe en un v´ertice del conjunto {a1, a2, . . . , aK} y que no se encuentra ning´un v´ertice interno. Debido a las restricciones con las que un ciclo Hamiltoniano recorre la componente de testeo de recubrimiento, esta parte del ciclo debe pasar por un conjunto de componentes de testeo de recubrimiento correspondientes exactamente a una de las aristas de Eque son incidentes en alg´un v´ertice v∈V. Cada componente de testeo de recubrimiento se recorre de una de las formas 2.14a, 2.14b o 2.14c que aparece en la figura 2.14 y no se encuentra con ning´un otro v´ertice de otra componente. Por lo tanto, los Kv´ertices de {a1, a2, . . . , ak}dividen el ciclo Hamiltoniano en Kcaminos cada uno de los cuales corresponde a un v´ertice distinto v∈V. Como cada ciclo Hamiltoniano debe incluir todo los v´ertices de cada componente de testeo de recubrimiento y como los v´ertices de estas componentes por cada arista e∈Epueden pasar solo por un camino correspondiente a un extremo de e, cada arista de Edebe tener al menos un extremo entre los Kv´ertices seleccionados. En consecuencia, este conjunto de Kv´ertices forma el recubrimiento buscado para G. 2.4. Problemas NP-completos cl´asicos 39 Figura 2.15: Uni´on por caminos de las componentes de teste de cubrimiento correspondientes a las aristas de Eque tienen al v´ertice vcomo extremo. Rec´ıprocamente, sea V∗⊂Vun recubrimiento de v´ertices de Gcon |V∗| ≤ K. Al a˜nadir v´ertices a V∗hasta conseguir |V∗|=Kse seguir´a teniendo un recubrimiento de v´ertices de G, luego podemos suponer que |V∗|=K. Sean v1, v2, . . . , vKlos elemento de V∗. Se tomar´an las siguientes aristas de G′para formar el ciclo Hamiltoniano para G′. Para la componente correspondiente a e={u, v}se elige la forma de recorrer las aristas 2.14a,2.14b o 2.14c dependiendo de si {u, v} ∩ V∗es {u},{u, v}o{v}, respectivamente. Estas son las tres ´unicas posibilidades posibles ya que V∗es un recubrimiento de v´ertices de G′. Finalmente, se toman las aristas: {ai,(vi, evi[1],1)},1≤i≤K, {ai,(vi+1, evi[gr(v)],6)},1≤i≤K y {a1,(vK, evk[gr(vK)],6)} Por lo tanto VC ≤pCH. 2.4.5. Partici´on En esta secci´on se ver´a que Partici´ on es un problema de optimizaci´on NP-completo. El problema de Partici´ on se define de la siguiente manera: dado un conjunto de n´umeros enteros positivos, ¿es posible dividirlos en dos subconjuntos de manera que la suma de los elementos en cada conjunto sea la misma? Para entender mejor el problema, supongamos que tenemos una lista de n´umeros enteros positivos como {1,2,3,4,5,6,7}. En este caso, una soluci´on podr´ıa ser dividir la lista en {1,2,4,7}y{3,5,6}, ya que la suma de los elementos en cada subconjunto es 14. El problema Partici´ on tiene inter´es pues es ´util a la hora de analizar la NP-completitud de problemas en los que aparecen par´ametro num´ericos tales como medidas de peso o altura, costes, capacidades, etc. 40 2. Introducci´on a la NP-completitud Partici´on Instancia: un conjunto finito A∈Zy una funci´on s:A→Z+. Pregunta: ¿Contiene Aun subconjunto A′tal que X a∈A′ s(a) = X a∈A−A′ s(a) ? La funci´on sque aparece en la instancia com´unmente tiene que ver con la forma de medir la magnitud de los elementos de A. Teorema 2.11. Partici´ on es NP-completo. Demostraci´on. Sea un A∈Zconjunto finito. Para ver que Partici´ on es NP-completo basta generar un subconjunto de Aen la fase no determinista y comprobar que la suma de s aplicada a sus elementos es igual la suma saplicada a los elementos de su complementario, lo cual se realiza en tiempo polinomial. A continuaci´on se reducir´a 3DM a Partici´ on. Sean X, Y yZtres conjuntos finitos disjuntos de igual cardinalidad q, y sea W⊂X×Y×Zcorrespondientes a una instancia arbitraria de 3DM. Se denotar´an los elementos de cada conjunto como sigue: X={x1, x2, . . . , xq} Y={y1, y2, . . . , yq} Z={z1, z2, . . . , zq} W={w1, w2, . . . , wk} donde k=|W|. El objetivo para completar la prueba ser´a construir un conjunto Ay una funci´on s:A→Z+, tal que Acontenga un subconjunto A′satisfaciendo : X a∈A′ s(a) = X a∈A−A′ s(a) si y solo si Wcontiene una correspondencia. El conjunto Acontendr´a k+ 2 elementos en total y se construir´a en dos pasos. Los primeros kelementos de Ason {ai: 1 ≤i≤k}, donde aiest´a asociado con la terna wi∈W. La funci´on sse concretar´a dando su representaci´on en binario, en t´erminos de una cadena de 0′sy 1′sdivididos en 3q“zonas” de p=⌈log2(k+ 1)⌉bits cada una. De nuevo, cada una de estas zonas est´a identificada por un elemento de X∪Y∪Z, como se muestra en la figura 2.16. Figura 2.16: Etiquetado de las 3qzonas, cada una de las cuales contiene p= log2(k+ 1) bits de la representaci´on en binario de s(a), usado para reducir 3DM a Partici´ on. 2.5. Problemas adicionales: M´etodos para probar la NP-completitud de un problema 41 La representaci´on de s(ai) depende de la terna wi= (xf(i), yg(i), zh(i))∈W(donde f, g y hson funciones de los sub´ındices de los wi). Esta tiene un 1 en el bit m´as a la derecha de las zonas identificada con xf(i), yg(i)yzh(i), y 0′ses las dem´as posiciones. Equivalentemente, esto se puede escribir como: s(ai) = 2p(3q−f(i)) + 2p(2q−g(i)) + 2p(q−h(i)) Como para expresar s(ai) en binario se usan a lo m´as 3pq bits, s(ai) puede ser construido en tiempo polinomial dada una instancia de 3DM. Lo que se debe tener en cuenta de esta parte de la construcci´on es que si sumamos todas las entradas de cualquier zona sobre todos los elementos {ai: 1 ≤i≤k}, el total nunca superar´a k= 2p−1. Por lo tanto, al sumar Pa∈A′s(a) para cualquier subconjunto A′⊂ {ai: 1 ≤i≤k}, no habr´a ninguna llevada de una zona a la siguiente. Se sigue que si hacemos B= 3q−1 X j=0 2pj (el cual es un n´umero cuya representaci´on en binario tiene un 1 en el lugar m´as a la derecha de cada zona), entonces cualquier subconjunto A′⊂ {ai: 1 ≤i≤k}satisfar´a X a∈A′ s(a) = B si y solo si M={ai:ai∈A′}es una correspondencia para W. El ´ultimo paso de la construcci´on describe los dos ´ultimos elementos de A. Estos ser´an denotados como b1y b2,sact´ua sobre ellos de la siguiente manera: s(b1) = 2k X i=1 s(ai)−B y s(b2) = k X i=1 s(ai)+B Como ambos pueden ser escritos en binario con no m´as de 3pq + 1 bits, se pueden construir en tiempo polinomial dada una instancia de 3DM. Sea A′⊂Atal que X a∈A′ s(a) = X a∈A−A′ s(a) Se tiene que las dos sumas valen 2 Pk i=1 s(ai) y uno de los dos conjuntos, A′oA−A′, contiene a b1pero no a b2. Se sigue que los elementos restantes del conjunto forman un subconjunto de {ai: 1 ≤i≤k}cuya suma al aplicarle svale B, y por tanto este subconjunto es una correspondencia de W. Rec´ıprocamente, si M⊂Wes una correspondencia, entonces el conjunto {b1}∪{ai:wi∈M}forma el conjunto A′buscado en la instancia de Partici´ on. Se concluye que 3DM ≤pPartici´ on. 42 2. Introducci´on a la NP-completitud 2.5– Problemas adicionales: M´etodos para probar la NP - completitud de un problema Las t´ecnicas usadas para probar la NP-completitud de un problema son tan variadas como la cantidad de problemas NP-completos existentes. Sin embargo, en muchos casos es ´util saber alguna de estas tres reglas: restricci´on, reemplazamiento local o dise˜no de componentes. En esta secci´on, se explicar´a como se usan en las demostraciones las t´ecnicas anteriores y se dar´an algunos ejemplos. Mientras que en algunas ocasiones varias de estas reglas aparecen en alg´un paso de la demostraci´on, en otras, puede que ninguna sea v´alida a la hora de afrontar el problema. Por lo tanto, esto no da una clasificaci´on de los problemas NP-completos, simplemente es una ayuda para detectarlos. En el transcurso de las siguientes secciones se omitir´a probar que los problemas pertenecen a NP con el motivo de aligerar las demostraciones. Los algoritmos para ver si un problema est´a en NP son similares al de los problemas tratados anteriormente as´ı que en este caso no se parar´a a mostrarlos expl´ıcitamente. 2.5.1. Restricci´on Las pruebas por restricciones suelen ser las m´as simples y, a´un as´ı, las m´as usadas. Dado Π ∈NP, una prueba de NP-completitud por restricci´on consiste en demostrar que Π contiene un problema NP-completo Π′como caso particular. El groso de esta prueba est´a en dar las restricciones adecuadas a las instancias de Π para que el problema resultante sea equivalente a Π′. No es necesario que los dos problemas sean id´enticos, sino que exista una correspondencia uno a uno entre sus instancias que respete las respuestas “s´ı” y “no”. El problema Recubrimiento exacto por conjunto de tres constituye un ejemplo de este tipo. El problema dice lo siguiente: Cubrimiento exacto por conjunto de tres (X3C) Instancia: Un conjunto finito Xtal que |X|= 3qcon q∈Ny una colecci´on Cde subconjuntos de Xde tres elementos. Pregunta: ¿Contiene Cun subconjunto que recubra exactamente a X, es decir, existe C′⊂Ctal que cada elemento de Xaparece ´unicamente en un elemento de C′? Teorema 2.12. X3C es NP-completo. Demostraci´on. Se probar´a la NP-completitud del problema reduciendo 3DM a X3C. Para ello solo hay que darse cuenta que toda instancia de 3DM puede ser vista como una de X3C consider´andola como un subconjunto conjunto no ordenado de X∪Y∪Z, es decir, las ternas de Wpasan a ser subconjuntos de C(figura 2.17). De esta forma las correspondencias de la instancias de 3DM se identifican uno a uno con los conjuntos recubridores de tres elementos como podemos ver en la figura 2.18. Otro de los problemas en los que se aplica este m´etodo es en Planificaci´ on de Multiprocesadores. Este problema consiste en estudiar, dados un conjunto de tareas con una determinada duraci´on, un conjunto de procesadores y un tiempo l´ımite, si es posible distribuir las tareas entre los distintos procesadores de manera que todas se finalicen antes del tiempo establecido. 2.5. Problemas adicionales: M´etodos para probar la NP-completitud de un problema 43 Figura 2.17: Transformaci´on de una instancia de 3DM a una instancia de X3C. X×Y×Z pasa ser X∪Y∪Zy las ternas del conjunto Wse convierten en los subconjuntos de tres elementos de C. Figura 2.18: Soluci´on del problema. Se observa que la respuesta “s´ı ” para 3DM se mantiene para X3C. Planificaci´on de multiprocesadores Instancia: un conjunto finito Ade tareas, una funci´on d:A→Nque indica la duraci´on de la tarea, m∈Nprocesadores, y Dun tiempo l´ımite. Pregunta: ¿Existe un partici´on A=A1∪A2∪... ∪Amde Aen msubconjuntos disjuntos tal que maxX a∈Ai d(a) : 1 ≤i≤m≤D? Teorema 2.13. Planificaci´ on de Multiprocesadores es NP-completo. Demostraci´on. Para probar que Planificaci´ on de Multiprocesadores es NP-completo bastar darse cuenta de que si restringimos el problema instancias en las que m= 2 y D=1 2X a∈A d(a) se obtiene el problema Partici´ on que es NP-completo. Como se ha podido observar en este tipo de pruebas la dificultad no recae en la prueba si no en saber el problema NP-completo al que se restringir´a. Muchos de los problemas que aparecen en la pr´actica no son m´as que una versi´on m´as completa de alg´un problema ya 50 3. Aplicaciones de la NP-completitud y fronteras entre las clase PyNP algunas tareas para poder ser completadas necesitan de la finalizaci´on de otras: Programaci´on restringida por Precedentes Instancia: Un conjunto Tde tareas (de igual duraci´on, se puede suponer d(t) = 1 para todo t∈T), un orden parcial ⋖en T, un n´umero mde procesadores, y un plazo D∈N. Pregunta:¿Existe una programaci´on σ:T→ {1,2, . . . , D}tal que, para cada i∈ {1,2, . . . , D},|{t∈T|σ(t) = i}| ≤ my cumpliendo σ(t)≤σ(t′) si t⋖t′? Este problema es el que un estudiante tiene que resolver en su primer a˜no en una universidad en la que cada curso se ofertara cada cuatrimestre y no hubiera solapamiento de horas entre los cursos elegidos. De un conjunto Tde asignaturas debe elegir como m´aximo mde ellas de forma que le de tiempo a acabar el grado menos de Dcuatrimestres. Adem´as, algunas de las asignaturas precisan de los conocimientos de otras, se dice que t⋖t′si para cursar la asignatura t′se necesita haber cursado tpreviamente. El objetivo es dise˜nar un algoritmo que nos permita en tiempo polinomial, a partir de la informaci´on anterior, planificar cada cuatrimestre. Se conoce que el problema de Programaci´ on restringida por Precedentes es NP-completo. Se puede consultar una prueba de este hecho en [19]. Por lo tanto, suponiendo que P=NP, ser´ıa improbable que se d´e un algoritmo de planificaci´on en tiempo polinomial. Sin embargo, restricciones razonables pueden ser aplicadas a las instancias, como, por ejemplo, que un alumno no curse m´as de 6 asignaturas por cuatrimestre, es decir, m≤6. Tambi´en puede ocurrir que un alumno haya elegido asignaturas tan variadas que no necesiten de de prerrequisitos, luego el orden es vac´ıo. En otras ocasiones cada curso necesita un ´unica prerrequisito dando lugar a un orden parcial en forma de ´arbol. En la figura 3.2 se describen los subproblemas posibles. Figura 3.2: Conocimiento actual del problema de Programaci´ on restringida por Precedentes. La figura 3.2 es un ejemplo concreto 3.1, en la que vuelven a aparecer tres tipos de problemas: los NP−completos, los Py los de la frontera. Cuando tenemos una red de subproblemas como esta, con frecuencia es posible definir la informaci´on de manera m´as concisa especificando el problema NP-completo “minimal” y el problema P“maximal”. Dada una colecci´on Cde subproblemas de un problema NP-completo, se dice que Π ∈C es un subproblema NP-completo minimal si es NP -completo y no se conoce ning´un otro subproblema Π′de Π en C. Por otra parte, se dice que un problema Π ∈Ces maximal si Π est´a en Py no existe ning´un otro problema de Cque tenga como subproblema a Π y 3.1. An´alisis de subproblemas 51 pertenezca a P. An´alogamente, se definen los problemas abiertos maximales y minimales. En la clase de subproblemas de Programaci´ on restringida por Precedentes ilustrada en la figura 3.2 , los dos que cumplen “⋖arbitrario, m≤2” y “⋖en ´arbol, m arbitrario” son maximales resolubles en tiempo polinomial. El problema general es en s´ı minimal NP-completo. El problema abierto minimal es el dado por ⋖arbitrario, m≤3” y no existe problema abierto maximal porque ⋖arbitrario, m≤J” est´a abierto para todo lo enteros J≤3. Por esto, a la hora de investigar la frontera, puede ser muy ´util tratar tanto con los problemas que tienen m´as pinta de estar en Pcomo con aquellos que pueden ser NP- completos. Tomando como punto de partida los subproblemas que obviamente se pueden resolver en tiempo polinomial y aquellos cuya NP-completitud se siga directamente del problema general, se puede gradualmente aumentar el conjunto de instancias permitidas para los primeros y las restricciones a los segundos. A diferencia de analizar un problema fijo, cuando se pasa de la b´usqueda de algoritmo polinomiales a probar NP-completitud, tambi´en se cambia de un problema m´as restringido a uno m´as relajado. Como se ha visto en el transcurso del trabajo los problemas de teor´ıa de grafos tienen un gran importancia en el estudio de la NP-completitud. Esta secci´on concluir´a con otro de estos problemas que ejemplificar´a lo que hemos visto en el p´arrafo anterior. 3-Colorabilidad Instancia: un grafo G= (V, E). Pregunta:¿Es G3-coloreable, es decir, existe una funci´on f:V→ {1,2,3}tal que f(u)=f(v) si {u, v} ∈ E? El problema constituye, a su vez, un subproblema de K−Colorabilidad en la cual la funci´on ftoma valores en {1,2, . . . , K}. En la referencia [17] est´a probada su NP- completitud. A continuaci´on se impondr´an restricciones y se estudiaran otros subproblemas. La primera restricci´on que se considera es la de acotar el grado de los v´ertices. La mayor´ıa de los problemas de teor´ıa de grafos pasan a estar en Pcuando se restringe a 2 es grado de los v´ertices. Por ejemplo, bajo esa restricci´on los problema Ciclo Hamiltoniano,Vertex Cover y 3−Colorabilidad pasan trivialmente a poder ser resueltos en tiempo polinomial. Aparece la pregunta: ¿Cu´al es la restricci´on m´as fuerte que podemos imponer al grado de los v´ertices para que el subproblema siga siendo NP-completo? El problema Clique es uno de los ejemplos para los que no existe una cota que preser- ve la NP-completitud. Sea Dla cota para el grado, cualquier clique del grafo no puede contener m´as de D+ 1 v´ertices. Por lo tanto, podemos buscar los cliques examinando los subconjuntos de D+ 1 o menos elementos, y el n´umero de subconjuntos est´a polinomialmente acotado pues Des una constante fija. Para muchos otros problemas de teor´ıa de grafos hay restricciones en el grado para las que los problemas siguen siendo NP-completos. La tabla 3.2 muestra algunos de estos problemas. En Ppara D≤NP-completo para D≥ Vertex Cover 2 3 Ciclo Hamiltoniano 2 3 3-Colorabilidad 2 4 Tabla 3.2: Clasificaci´on de problemas de teor´ıa de grados en funci´on del grado de Dde sus v´ertices. 52 3. Aplicaciones de la NP-completitud y fronteras entre las clase PyNP La NP-completitud de los problemas de la derecha de la tabla puede ser probada por reemplazamiento local de manera similar. Para ejemplificarlo se usar´a 3−Colorabilidad. Teorema 3.1. 3−Colorabilidad con v´ertices de grado menor o igual que 4es NP- completo. Demostraci´on. Como el problema general est´a en NP este tambi´en lo estar´a. Sea G= (V, E) una instancia del problema general. Se construir´a otro grafo G′= (V′, E′) cuyos v´ertices tengan grado menor o igual que 4 y que sea 3-coloreable si y solo si Ges 3- coloreable, obteniendo as´ı la reducci´on deseada. La sustituci´on realizada se basa en un grafo de 8 v´ertices H3que se ilustra en la figura 3.3a, que tiene 3 salidas, etiquetadas por 1,2 y 3 en la figura. Para k≥4, el v´ertice de k-salida se sustituye por Hkformado al unir Hk−1con una copia de H3cuya primera salida coincide con la la salida k−1 de Hk−1. Los v´ertices de salida de Hktienen grado dos. Las salidas originales de Hk−1mantienen las mismas etiquetas, uniendo un H3en el v´ertice de salida k−1 y convirtiendo la tercera salida de H3en la salida k. En la figura 3.3b se muestra la construcci´on de H5, es decir, el grafo que sustituye a los v´ertices de grado 5. (a) Grafo H3. (b) Grafo que sustituye a un v´ertice de grado 5. Figura 3.3 De la construcci´on se deducen los siguiente resultados: 1. Hktiene 7(k−2) + 1 v´ertices, incluyendo los kv´ertices de salida etiquetados. 2. Ning´un v´ertice de Hktiene grado mayor que 4. 3. Los v´ertices de salida de Hktienen grado 2. 4. Hkadmite una 3-coloraci´on pero no una 2-coloraci´on que, adem´as, asigna el mismo color a los v´ertices de salida. Sea v1, v2, . . . , vrlos v´ertices del grafo Gde grado mayor que 4. Se construye la siguiente sucesi´on de grafos: G=G0, G1, G2, . . . , Gr=G′ por la siguiente recurrencia. Sea del grado de vien Gi−1y sean {u1, vi},{u2, vi},...,{ud, vi} la aristas incidentes en vi. Para forma Gi, se elimina de Gi−1el v´ertice vi, se intercambia por una copia de Hdy la arista {uj, vi}se reemplaza por una arista que une ujcon el v´ertice de salida jde Hd. 3.2. 2SAT est´a en P53 Por construcci´on y por las deducciones anteriores Gkcon 1 ≤k≤rtiene r−kv´ertices de grado mayor que 4 y Gkes 3-coloreable si y solo si Glo es. Por lo tanto, Gr=G′es el grafo buscado. Aunque, gran variedad de sustituci´on de v´ertices pueden ser aplicadas a los distintos subproblemas de teor´ıa de grafos, este ejemplo da una idea de como proceder con los dem´as. 3.2– 2SAT est´a en P Anteriormente, se estudi´o la NP-completitud del problema SAT. Despu´es se vio como con una reducci´on adecuada 3SAT tambi´en es NP-completo. Sin embargo, cuando se restringe a dos el tama˜no de las cl´ausulas, pasando as´ı a 2SAT, resulta un problema perteneciente a la clase P. 2SAT ofrece un interesante caso de donde se establecen las posibles fronteras entre PyNP. El prop´osito de esta secci´on es probar que 2SAT est´a en P. Para ello se probar´a, en primer lugar, que el problema Camino es tratable y, posteriormente, se da dar´a una reducci´on polinomial de Camino a 2SAT que est´a inspirada en la que aparece en [11]. Camino Instancia: Sean G= (V, E) un grafo dirigido y sytdos nodos. Pregunta: ¿Existe un camino entre syt? En un primer intento de la b´usqueda de un algoritmo para Camino se podr´ıa pensar en recorrer todos los posibles caminos. Si el grafo tiene nv´ertices por cada v´ertice se podr´ıan tener nopciones a seguir, lo que da una complejidad de nn. En la prueba del teorema 3.2 se obtiene un algoritmo m´as sofisticado que permite probar que Camino est´a en P. Teorema 3.2. Camino est´a en P. Demostraci´on. Sean G= (V, E) un grafo dirigido, y sytdos nodos, se tiene que decidir si existe o no un camino entre syt. El algoritmo utilizar´a las colas, una estructura de datos en la cual se permiten a˜nadir elementos al final de la cola y eliminar elementos del principio. El algoritmo sigue los siguientes pasos: 1. Marca el nodo sy se a˜nade a la cola. 2. Mientras la cola no est´e vac´ıa: a) Elimina el primer nodo yde la cola. b) Para toda arista (y, u) tal que uno est´a marcado, marca uy a˜nade ual final de la cola. 3. Aceptar si test´a marcado. El algoritmo es correcto pues si test´a marcado quiere decir que hay un camino desde s at. Se estudia ahora la complejidad en tiempo del algoritmo. La cola puede ser usada pues a˜nadir y eliminar elementos de la misma ocupa tiempo constante. Cada nodo se a˜nade como m´aximo una vez a la cola. Por lo tanto, una cota superior para el tiempo de ejecuci´on es la dada por la suma sobre todos los nodos ydel tiempo requerido para comprobar los nodos adyacentes a y. Si el grafo Gtiene nv´ertices y maristas, y est´a dado en t´erminos 54 3. Aplicaciones de la NP-completitud y fronteras entre las clase PyNP de su matriz de adyacencia, se tiene una cota de O(n2) y si Gest´a dado por su lista de adyacencia, se obtiene una cota de O(n+m), pues cada arista solo se comprueba una vez. En ambos casos la complejidad es polinomial, como se quer´ıa demostrar. Teorema 3.3. 2SAT est´a en P Demostraci´on. Se reducir´a 2SAT a Camino. Sean U={u1, u2, . . . , um}un conjunto finito de variables booleanas y Cuna colecci´on de cl´ausulas de dos literales cada una. A partir de esta instancia, se construir´a el siguiente grafo dirigido: •Por cada variable ujcon 1 ≤j≤mse a˜naden a Gdos v´ertices, uno correspondiente aujy, otro, a uj. •Por cada cl´ausula {x1, x2}, se a˜naden a Glas aristas (x1, x2) y (x2, x1). Estas ´ultimas aristas hacen el papel de implicaciones l´ogicas. Por ejemplo, consid´erese la cl´ausula {u1, u2}y se supone que la asignaci´on de verdad testable que t(u1) = T. Como es necesario que al menos uno de los dos literales de la cl´ausula sea verdadero, esto implicar´ıa que t(u2) = V. En la figura 3.4 se muestra un ejemplo. Figura 3.4: Grafo obtenido a partir de C={{u1, u2},{u2, u3},{u1, u3},{u2, u3}}. Seguidamente, se mostrar´a que Cno es satisfactible si y solo si para alg´un 1 ≤j≤m existe en Gun camino de ujaujy de ujauj (⇐) Por reducci´on al absurdo, se supone que existe un camino de ujaujy de ujauj. Si t(uj) = T, entonces t(uj) = 0, entonces debe existir una arista (x1, x2) en el camino desde ujaujtal que t(x1) = Tyt(x2) = F. Esto implica que {x1, x2}es una cl´ausula de Cque no es satisfecha por t. Para el caso t(uj) = F, se razona de forma an´aloga. 3.3. Implicaciones de P=NP: Existencia de problemas NP-intermedios 55 (⇒) Se construir´a un m´etodo para encontrar una asignaci´on de verdad satisfactible para Cdando valores de verdad a los v´ertices de G. Reiteradamente, para cada v´ertice x que no tiene valor asignado y tal que no existe un camino de xax, se le asigna el valor Taxy a los v´ertices a los que se puede llegar desde x; y se le asigna Fax y a la negaci´on de v´ertices a los que se puede llegar desde x, es decir, a los que se puede llegar desde x. En primer lugar, se comprueba que el proceso de construcci´on est´a bien definido. Si alg´un camino desde xa dos v´ertices yyy, entonces por simetr´ıa de Ghabr´ıa un camino de yyyax, as´ı que habr´ıa un camino de xax, contradiciendo la hip´otesis. Por lo tanto los valores de verdad se asignan de forma consistente. Adem´as, si hay un camino de xa un v´ertice yque ha sido asignado con F, por ejemplo, como se puede llegar a ydesde x,xdebe haber sido asignado con F. Como se ha asumido que para cada variable uj, no hay ning´un camino de ujaujni de ujauj, todas las ujtendr´an un valor de verdad asignado. Como la asignaci´on de verdad se produce de tal manera que cada vez que aparezca la arista (x, y), o bien a yse le asigna To a xse le asigna F, la asignaci´on satisface C. Una vez hecho esto, se puede finalizar aplicando el algoritmo de Camino a cada par uj yuj, lo cual se completa en tiempo polinomial. 3.3– Implicaciones de P=NP: Existencia de problemas NP - intermedios Muchos de los problemas de NP que han sido estudiados en las ´ultimas d´ecadas han resultado ser, sorprendentemente, NP-completos. Est´e fen´omeno sugiere la siguiente conjetura: “Todo problema de NP es NP-completo”. En esta secci´on, se mostrar´a que, bajo la asunci´on de que P=NP, la conjetura anterior es falsa, es decir existe un lenguaje de NP −Pque no es NP-completo. Este resultado es conocido como “Teorema de Ladner”. Esta demostraci´on est´a tomada de [1]. Teorema 3.4. Si P=NP, entonces existe un lenguaje L∈NP −Pque no es NP- completo. Demostraci´on. En esta prueba se usar´a un esquema de codificaci´on cuyo alfabeto de entrada es Σ = {0,1}. Si P=NP, se conoce al menos un lenguaje que pertenece a NP −P; el lenguaje asociado al problema de decisi´on SAT, LSAT . Para cada H:N→N, se define un lenguage SATHque contiene a todos los conjuntos de cl´ausulas con ncl´ausulas con nH(n)1′s concatenados, esto es: SATH={ψ0(1)nH(n):ψ∈SAT y n =|ψ|} Se define una funci´on H:N→Nconcreta como sigue: H(n) es el menor n´umero i < log log(n) tal que para todo x∈ {0,1}∗con |x| ≤ log n,Midevuelve SATH(x) en i|x|i pasos.(Mies la m´aquina que corresponde a la expansi´on binaria de i, y SATH(x) = 1 si y solo si x∈SATH). Si no existe tal ientonces H(n) = log log n. 56 3. Aplicaciones de la NP-completitud y fronteras entre las clase PyNP Hest´a bien definida pues H(n) determina la pertenencia a SATHde cadenas cuya longitud es mayor que n, y la definici´on de H(n) depende ´unicamente de comprobar el estado de las cadenas de longitud a los m´as log(n). Se afirma que SATH∈Psi y solo si H(n) = O(1)(es decir, existe C > 0tal que H(n)≤Cpara todo n). Adem´as, si SATH/∈Pentonces H(n)tiende a infinito cuando n tiende a infinito Demostraci´on de la afirmaci´on: (⇒) Sea Muna m´aquina que resuelve SATHen cncpasos como m´aximo. Como M est´a representada por infinitas cadenas, debe existir i>ctal que M=Mi1. La definici´on de H(n) implica que para n > 22idebe ocurrir que H(n)≤i. Por lo tanto, H(n) = O(1). (⇐) Si H(n) = O(1) entonces Hsolo puede tomar una cantidad finita de valores, y por lo tanto, existe un ital que H(n) = ipara infinitos n. Pero esto implica que la m´aquina de Turing Miresuelve SATHen tiempo ini: de lo contrario, si habr´ıa una entrada xen la que Mino diera la respuesta correcta en bajo esa cota de tiempo, para todo n > 2|x|se tendr´ıa que H(n)=i. Esto se mantiene si H(n)≤Cpara infinitos n, probando as´ı el adem´as de la afirmaci´on. Usando la afirmaci´on se probar´a que si P=NP entonces SATHno est´a ni en Pni es NP completo: •Si SATH∈P, entonces la afirmaci´on nos dice que H(n)≤Cpara alguna constante C > 0, esto implica que SATHes simplemente SAT con una cantidad polinomial de 1′sconcatenados. Pero entonces un algoritmo polinomial para SATHpodr´ıa usarse para resolver SAT en tiempo polinomial, implicando P=NP, lo que contradice la hip´otesis. •Si SATHfuera NP-completo existir´ıa una reducci´on de SATHa SAT en tiempo polinomial O(ni) para cierto i. Como SATH/∈P, por la afirmaci´on anterior se tiene que H(n) tiende a infinito cuando ntiende a infinito. Como la reducci´on se completa en tiempo O(ni), para nsuficientemente grande debe hacer corresponder instancias de tama˜no ncon instancias de SATHde tama˜no menor que nH(n). Por lo tanto, para f´ormulas suficientemente grandes φ, la reducci´on flas env´ıa en cadenas del tipo ψ0(1)nH(|ψ|)donde ψes menor que un factor polinomial adecuado, por ejemplo, 3 √n. Pero la existencia de dicha reducci´on lleva a un algoritmo polinomial para SAT, contradiciendo que P=NP. 3.4– Implicaciones de P=NP Las anteriores secciones de este cap´ıtulo ponen su esfuerzo en probar que P=NP. Pero, ¿que ocurrir´ıa si P=NP ? En esta secci´on se desarrollaran algunas de las implicaciones te´oricas y pr´acticas de P=NP, para as´ı poder mostrar la importancia del problema. El hecho de que P=NP es una posibilidad, pero en la pr´actica no se cuenta con algoritmos polinomiales para problemas NP-completos. Se va suponer que estos algoritmos si existen y se conocen, y se ver´a que ocurre al hacer uso de ellos. 1Mies la M T N D asociada el leguage codificado por i. 3.5. Otros enfoques para demostrar P=NP 57 Uno de los avances m´as notables se producir´ıa en el campo de la optimizaci´on pues muchos de sus problemas son NP-completos. Esto tendr´ıa un impacto significativo en la eficiencia de la sociedad, desde el transporte hasta la producci´on de bienes. El transporte de personas y mercanc´ıas se optimizar´ıa para ser m´as r´apido y econ´omico, y los fabricantes podr´ıan mejorar su producci´on para aumentar la velocidad y reducir el desperdicio. La inteligencia artificial avanzar´ıa a paso agigantados gracias a la cantidad de problemas de la teor´ıa de grafos que podr´ıan ser resueltos en tiempo polinomial. Por contra, un problema surgir´ıa en la ciberseguridad actual pues cualquier esquema de encriptaci´on tendr´ıa un algoritmo de decodificaci´on trivial, lo que significar´ıa la falta de privacidad en el ´ambito digital. No existir´ıan sistemas de dinero digital, SSL, RSA o PGP. Si se verifica la igualdad, se podr´ıan encontrar demostraciones l´ogicas cortas para los teoremas matem´aticos: se podr´ıa encontrar la teor´ıa m´as simple que explique un conjunto de datos experimentales o informaci´on disponible. Esto se basar´ıa en el principio de la Navaja de Occam, que postula que la explicaci´on m´as simple es probablemente la correcta. Stephen Cook afirm´o que si se encontrara un algoritmo eficiente para resolver problemas NP-completos las matem´aticas cambiar´ıan dr´asticamente pues permitir´ıa a los ordenadores dar pruebas a teoremas de longitud razonables, pues las pruebas se pueden comprobar en tiempo polinomial, generalmente. En resumen, el mundo actual cambiar´ıa dr´asticamente y habr´ıa que comenzar a pensar en nuevas t´ecnicas que permitan tanto tomar ventaja de este problema: encontrar soluciones eficientes para antiguos problemas NP-completos y ponerlas en pr´actica; como defendernos de los posibles perjuicios: buscar nuevos sistemas de ciberseguridad. 3.5– Otros enfoques para demostrar P=NP Como bien se ha mencionado a lo largo del cap´ıtulo, la comunidad cient´ıfica se inclina por pensar que P=NP, no solo por la cantidad de problemas de los que no se puede hallar un algoritmo eficiente, sino por la Utop´ıa te´orica que plantear´ıa. Para concluir el cap´ıtulo, se mostrar´an diferentes maneras de las que se ha tratado probar P=NP y han fallado en el intento. En [5] se pueden encontrar m´as detalles sobre este tema. Diagonalizaci´on Este m´etodo responde a la pregunta de si puede encontrar un lenguaje Lconcreto de forma que todo algoritmo polinomial fallara al computar Len alguna entrada. Este planteamiento se conoce como diagonalizaci´on y tiene sus inicios en el siglo XIX. La diagonalizaci´on es la t´ecnica que en 1874 Cantor us´o para demostrar que nos n´umero reales no son numerables. La diagonalizaci´on permiti´o a Cantor[4], dada un conjunto de numero reales numerable, construir otro que no estuviera en la lista. Turing, en su famoso art´ıculo sobre computaci´on [18], usa una estrategia parecida para demostrar que el problema de la Parada no es computable. En los sesenta los cient´ıficos de teor´ıa de la complejidad utilizaron la diagonalizaci´on para probar que si se contaba m´as tiempo y m´as memoria se pod´ıan resolver m´as problemas. ¿Por qu´e no usar la diagonalizaci´on pa separar NP de P? La diagonalizaci´on requiere de simulaci´on y en la actualidad no se comprende como una m´aquina no determinista fija puede simular una m´aquina determinista arbitraria. Adem´as una prueba por diagonalizaci´on tiende a relativizarse, es decir, que funcionar´ıa incluso si todas las m´aquinas involucradas tienen acceso a la misma informaci´on adicional 58 3. Aplicaciones de la NP-completitud y fronteras entre las clase PyNP o recursos. Baker, Gill y Solovay, en su trabajo citado [2], demostraron que ninguna prueba relativizable puede resolver el problema Pvs NP en ninguna direcci´on. Aun as´ı, la diagonalizaci´on se ha usado para probar que no pueden existir algoritmos por debajo de cierta complejidad en tiempo y en espacio para SAT, aunque esto dista mucho de probar que P=NP. Complejidad de f´ormulas Booleanas Para probar que P=NP es suficiente con hallar un problema NP-completo que no pueda ser resuelto con f´ormulas Booleanas con AND, OR o NOT relativamente limitas (el n´umero de operadores l´ogicos est´a acotado por una cierta constante fija). En 1984, Furst, Saxe y Sipser [6] demostraron que las f´ormulas limitadas no pueden resolver la funci´on de paridad si las f´ormulas tienen un n´umero fijo de capas de operadores. En 1985, Razborov [13] mostr´o que el problema NP-completo Clique no tiene este tipo de f´ormulas si solo se permiten operadores AND y OR (sin el operador NOT). Si se extiende el resultado de Razborov a circuitos generales, se habr´a demostrado que P es distinto de NP. Razborov prob´o m´as tarde que sus t´ecnicas fallar´ıan si se permit´ıa operadores NOT [14]. Razborov y Rudich [15] desarrollaron una noci´on de“pruebas naturales” y presentaron evidencia de que estas t´ecnicas no podr´ıan avanzar mucho m´as. Complejidad de demostraciones Una tautolog´ıa no es mas que una f´ormula booleana que se satisface para cualquier asignaci´on de verdad de sus variables. Existe un m´etodo llamado resoluci´on que constituye un enfoque est´andar para probar tautolog´ıas , mediante la b´usqueda de cl´ausulas de cierto formato y agregando nuevas cl´ausulas. Si se pudiera demostrar que las tautolog´ıas no tienen pruebas “cortas”, eso implicar´ıa que Pes distinto de NP. En 1985, Haken [8] demostr´o que las tautolog´ıas que codifican el principio del palomar (si hay m´as palomas que agujeros, entonces alg´un agujero tiene m´as de una paloma) no tienen pruebas de resoluci´on cortas. Desde entonces, los te´oricos han demostrado debilidades similares en otros sistemas de demostraciones, como el de planos de corte, sistemas de prueba algebraicos basados en polinomios y versiones restringidas de pruebas utilizando los axiomas de Frege. Para probar que Pes distinto de NP, se necesitar´ıa demostrar que las tautolog´ıas no tienen pruebas cortas en un sistema de pruebas arbitrario. Incluso un resultado importante que muestre que las tautolog´ıas no tienen pruebas generales de Frege cortas no ser´ıa suficiente para separar NP de P. CAP´ ITULO 4 Conclusiones y ampliaciones futuras A lo largo de este proyecto se ha dado una primera introducci´on al mundo de la NP- completitud as´ı como al problema del milenio Pvs NP, adem´as de haber visto su importancia en las matem´aticas y las ciencias de la computaci´on habiendo conseguido ser uno de los siete Problemas del Milenio que se remuneran con 1000000$. A continuaci´on, se aportar´an conclusiones y ampliaciones futuras. Primeramente, se han expuestos resultados de gran relevancia como el Teorema de Cook que consigue reducir toda m´aquina de Turing no determinista a un problema de l´ogica Booleana, SAT. Tambi´en se han explicado, algunas reducciones entre los problemas NP- completos cl´asicos de manera visual para facilitar su entendimiento. Esto ha confirmado la dificultad del resolver problemas NP-completos y la aparente inexistencia de un algoritmo eficiente para ello. La Teor´ıa de la Complejidad Computacional es un campo de estudio relativamente moderno que tuvo su inicio a mediados del siglo pasado con el desarrollo de las computadoras. Esto quiere decir que sus conceptos y su metodolog´ıa est´an en pleno desarrollo. De hecho, el gran Richard M. Karp[21], cient´ıfico en esta rama que ha proporcionado numerosas aportaciones a la misma, afirma que si alg´un d´ıa se resuelve este problema ser´a con conceptos que todav´ıa no han sido planteados en la actualidad. 4.1– Ampliaciones futuras Debido a que la resoluci´on del problema Pvs NP tendr´ıa implicaciones significativas en ´areas tan diversas como la criptograf´ıa, la inteligencia artificial, la optimizaci´on y la verificaci´on de software. Es fundamental continuar investigando y abordando el problema Pvs NP en busca de nuevas soluciones y avances en la teor´ıa de la computaci´on. Sin embargo, el campo de la teor´ıa de la complejidad es mucho m´as amplio que ´unicamente el problema Pvs NP. Por ejemplo, las computadoras constan con una memoria limitada, luego es importante que los algoritmos ocupen el menor espacio posible. De esta y otra inquietudes surge el concepto de complejidad en espacio. Por otra parte, las clases de complejidad no tienen por qu´e ser solo polinomiales sino que tambi´en existen algoritmos de otras complejidades como exponenciales o logar´ıtmicas, una imagen de esto puede verse en [9] donde aparecen todas las clases de complejidad y relaciones entre ellas, algunas de ellas probadas y otras conjeturadas. 59