Complejidad

Roberto Moriyón

Complejidad de algoritmos

• Un programa que calcula una función f(w) tiene complejidad F(m) si para cualquier cadena w, el número de instrucciones que se ejecutan para calcular f(w) es menor o igual que F(|w|).

• Podemos tomar F(m) como el mayor número de instrucciones que se emplea en calcular f(w) para palabras de longitud menor o igual que m.

• Ejemplo: El algoritmo de ordenación de la burbuja tiene complejidad 3m(m+1)/2.

for (i = 0; i <= N; i++) {for (j = N; j > i; j--) {if (v[j] > v[j-1]) {

switch(v[j], v[j-1]); } } }

Complejidad de algoritmos, II

• Un programa que calcula una función g(n) tiene complejidad G(m) si para cualquier número n, el número de instrucciones que se ejecutan para calcular g(n) es menor o igual que F(log2n)

• Ejemplo: El algoritmo manual para calcular el producto de números tiene complejidad m/2.

• Estamos atribuyendo una importancia uniforme al acceso a memoria aleatoria.

• Los factores se pueden codificar de varias formas (separador, potencia, …)

Complejidad de algoritmos, III

• Un programa tiene complejidad:– Lineal si tiene complejidad C.m para alguna

constante C.– Cuadrática si tiene complejidad C.m2 para

alguna constante C.– Polinomial si tiene complejidad P(m) para

algún polinomio P.– Exponencial si tiene complejidad C.em para

alguna constante C.

Complejidad de algoritmos, IV

• Ejemplo: el problema del viajante (Travel Salesman Problem, TSP)

• Hallar la ruta de longitud mínima que pasa por un conjunto dado de ciudades.

• Solución obvia: Para cada permutación de las ciudades:– Calcular la longitud de la ruta correspondiente.– Si el coste es menor que el mejor encontrado,

guardar coste y permutación.• Tiene complejidad exponencial.

Complejidad de algoritmos, V

• La definición de complejidad se puede extender a otros mecanismos computacionales que permiten definir funciones, como las máquinas de Turing deterministas.

Variación de la complejidad

• En general interesa calcular la solución de problemas, en los que hay que representar los datos de manera adecuada y buscar un mecanismo computacional y un algoritmo óptimos.

• Como referencia se suelen utilizar las máquinas de Turing como modelo de computación.

• La diferencia entre utilizar un algoritmo u otro relacionado con él normalmente es polinomial. (Ejemplos: cambio de base; cambio de mecanismo computacional).

Algoritmos intratables

• Se considera que un algoritmo es intratable si su complejidad es peor que polinómica.

• Por el contrario, los algoritmos con complejidad polinómica se consideran bastante aceptables.

• Los algoritmos con complejidad logarítmica se consideran como aceptables sin ninguna duda.

• En la práctica, dependiendo de las constantes de magnitud un algoritmo logarítmico o polinomico puede ser intratable.

Complejidad no determinista

• Se puede definir una noción de complejidad no determinista asociada a mecanismos computacionales que permiten reconocer conjuntos de datos, como las máquinas de Turing indeterministas y las gramáticas, como sigue:

Complejidad no determinista, II

• Una máquina de Turing que acepta un lenguaje L tiene complejidad no determinista F(m) si dada cualquier palabra w, alguna rama de ejecución de la máquina a partir de w activa a lo más F(|w|) transiciones antes de parar.

Complejidad no determinista, III

• Ejemplo: Problema SAT• Para reconocer al lenguaje formado por las

fórmulas proposicionales satisfactibles podemos utilizar una máquina que da valores booleanos indeterministamente a las proposiciones atómicas y calcula el valor de la expresión booleana resultante. La complejidad no determinista de esta máquina es polinómica. Es fácil construir una máquina de Turing determinista equivalente cuya complejidad es exponencial, pero no se sabe si hay alguna con complejidad polinómica.

Complejidad no determinista, IV

• Ejemplo: Variante del problema del viajante.• Determinar si hay alguna ruta de longitud

menor que L que pase por un conjunto dado de ciudades.

• La idea del algoritmo dado para el problema SAT se adapta de manera obvia.

• El algoritmo se puede ejecutar de manera indeterminista con respecto a las permutaciones, teniendo una complejidad polinomial.

• No se sabe si hay un algoritmo indeterminista polinomial que resuelva el problema.

Ejercicios

• Estudiar la complejidad indeterminista y la determinista de los siguientes problemas:– [NW] Palabras que contienen “ababa”.– [REP] Palabras que contienen dos copias de

alguna subpalabra de cinco letras.– [PAL] Palabras que no son palíndromes.– [EQUI] Descomponer un conjunto de números

en dos con la misma suma.– [COMP] Determinar si un número es compuesto

Ejercicios

• Estudiar la complejidad no determinista de los siguientes problemas:– [MINGRAF] Hallar un conjunto minimal de

vértices de un grafo que contenga al menos un vértice de cada arista.

– [MAXGRAF] Hallar un conjunto maximal de vértices de un grafo que están todos ellos conectados entre sí.

Problemas P y NP

• La clase P de problemas está formada por los problemas que tienen un algoritmo determinista que los resuelve con complejidad polinomial.

• La clase NP de problemas está formada por los problemas que tienen un algoritmo indeterminista que los resuelve con complejidad (no determinista) polinomial.

• Ejemplos: La ordenación de números es un problema P y NP. El problema SAT es un problema NP, pero no se sabe si es P. Lo mismo ocurre con el problema del viajante.

Reducción polinomial

• Una reducción polinomial de un algoritmo que calcula una función f(w) a otro que calcula g(w) es un tercer algoritmo determinista que calcula h(v) con complejidad polinómica y que verifica que f(w) = h(g(w)).

• Una reducción polinomial de un algoritmo que reconoce un lenguaje L a otro que calcula otro lenguaje M es un algoritmo que calcula h(w) con complejidad determinista polinómica y que verifica que L=h-1(M).

Reducción polinomial, II

• Si un problema se reduce polinomialmente a otro de la clase P, el primero también es de la clase P.

• Si un problema se reduce polinomialmente a otro de la clase NP, el primero también es de la clase NP.

Reducción polinomial, III

• Ejemplos:– La función f(w) cuyo valor es si el doble del

número de aes de w más el triple del número de bes de w es múltiplo de cinco y “a” en caso contrario tiene complejidad polinomial.

– El conjunto de palabras w tales que el doble del número de aes de w más el triple del número de bes de w es múltiplo de cinco tiene complejidad polinomial.

Reducción polinomial, IV

• Demostración:– Suponemos que c y d son símbolos que no

pertenecen al alfabeto inicial.– La función g(v) en (c+d)* cuyo valor es si |

v| es múltiplo de cinco y “a” en caso contrario tiene complejidad polinomial.

– La función f(w) es la composición h(g(v)), donde h es la función que sustituye cada a por cc y cada b por ddd, que tiene complejidad polinomial.

Reducción polinomial, V

• Ejemplo: Puzzle

• Un puzzle es una fórmula lógica que indica restricciones sobre los valores que pueden aparecer en un conjunto de fichas, enlazadas mediante conjunciones, disyunciones y negaciones.

• También podemos pensar en las fichas como variables, en cuyo caso el puzzle se convierte en una relación entre los valores de las variables.

Reducción polinomial, VI

• Ejemplo: Tomamos x, y, z como variables y 1, 2 como valores. Entonces:– La fórmula x=1 ^ ~x=y ^ ~y=z ^ z=2 define un

puzzle que no tiene solución.– La fórmula x=1 ^ ~x=y ^ ~y=z define un puzzle

que tiene una solución.

• El problema SAT es un caso particular de puzzle, donde los símbolos proposiciona-les son las variables y los valores son los booleanos true y false.

Reducción polinomial, VII

• Cualquier puzzle con variables xi y valores posibles rj equivale a la conjunción de la fórmula del puzzle con los siguientes conjuntos de fórmulas:– xi = r1 v xi = r2 v … v xi = rn

– xi = xj xj = xi

– xi = xj ^ xj = xk xi = xk

– xi = xj ^ xj = ra xi = ra

– xi = ra ~xi = rb si a≠b

Reducción polinomial, VIII

• La construcción anterior permite reducir la resolución de puzzles al problema SAT, utilizando los símbolos proposicionales siguientes:– Pi,j representa xi = xj

– Qi,a representa xi = ra

Reducción polinomial, IX

• Ejemplo: El problema SAT se puede reducir polinomialmente al problema CSAT de reconocimiento de las fórmulas proposicionales satisfactibles que están en forma normal conjuntiva.

• Observación: La demostración no es trivial, pues la forma habitual de transformar una fórmula proposicional arbitraria en otra equivalente en forma normal conjuntiva tiene complejidad exponencial.

Reducción polinomial, X

• Demostración de la reducción de SAT a CSAT:• Es consecuencia de la observación de que

(p1p2…pn)(q1q2…qm)es satisfactible si y sólo si

(p1X)(p2X)…(pnX)(q1~X)(q2~X)…(qm~X)

lo es. En esta transformación la longitud de la cláusula obtenida aumenta con respecto a la de la inicial en una cantidad fija por cada conjunción y cada disyunción. El método tradicional de paso a forma normal eleva al cuadrado el número de cláusulas.

Ejercicios

• [HAM] Se consideran los problemas1. Dado un grafo no dirigido, determinar si hay un

ciclo hamiltoniano, es decir que pase exactamente una vez por cada nodo del grafo inicial.

2. Problema del viajante: Dado un grafo no dirigido con pesos en las aristas, determinar si hay un ciclo hamiltoniano tal que la suma de los pesos de sus aristas sea menor que un número dado N.

Demostrar que 1 se pude reducir polinomialmente a 2 y viceversa.

NP completitud

• Un problema es NP completo si es NP y además cualquier otro problema NP se puede reducir a él.

• Los problemas NP completos son los más complejos entre los problemas NP, pues si alguno de ellos fuera P, todos los demás problemas NP lo serían.

Teorema de Cook

• El problema SAT es NP completo.• Idea de la demostración:

– Hay que ver que cualquier problema NP se puede reducir al problema SAT. Suponemos por lo tanto que M es una máquina de Turing no determinista cuyo algoritmo de reconocimiento asociado tiene complejidad P(m), donde P es un polinomio y que w es una palabra de longitud m, y denotamos M=P(m).

Teorema de Cook, II

• Suponemos que M es una máquina de Turing indeterminista fija con complejidad indeterminista P(m).

Teorema de Cook, III

• Por cada palabra w representaremos el hecho de que M acepte a w mediante un puzzle. Habrá NxN+|w| fichas (variables) e[i,j], donde N=P(|w|) es mayor que el número de pasos que da M partiendo de w antes de pararse al ir haciendo eleccio-nes consecutivas de transiciones y tam-bién es mayor que el tamaño del trozo de cinta sobre el que escribe M al ejecutarse.

Teorema de Cook, IV

• La variable ei,j representará el símbolo que hay sobre la cinta en el lugar j tras i pasos de la ejecución del camino elegido si el cabezal de M apunta en ese momento más a la derecha, o bien el estado de M si el cabezal apunta al j-ésimo símbolo de la cinta o el símbolo que hay sobre la cinta en el lugar j-1 si el cabezal apunta más a la izquierda.

Demostración del Teorema de Cook, V

• La fórmula lógica del puzzle que representa la aceptación de la palabra w por la máquina de Turing M es la conjunción de las tres siguientes:1) El estado inicial e0 de la máquina se representa en la forma p0w.2) Para cada k, el estado ek+1 de la máquina se obtiene a partir del estado ek aplicando alguna regla de transición.3) El estado final eN de la máquina es de bloqueo y aceptación.

Demostración del Teorema de Cook, VIII

• La fórmula 1) es simplemente

e0,0 = p0 ^ e0,1 = w0 ^ …

^ e0,|w| = w|w| ^ e0,|w|+1 = B ^ …

^ e0,N = B

y la denotaremos .

• La fórmula 3), , es análoga, pues hay solamente una cantidad finita de posibilidades para las letras que forman eN.

Demostración del Teorema de Cook, IX

• Para obtener una fórmula proposicional que represente a la afirmación 2) vemos en primer lugar que el hecho de que ek+1 se obtenga a partir de ek mediante una transición que pasa del estado p al q sustituyendo x por y y avanzando hacia la derecha se puede representar como sigue:

Teorema de Cook, X

ek,0 = ek+1,0 ^ ek,1 = ek+1,1 ^…

^ ek,j-1 = ek+1,j-1 ^ ek,j = p ^

^ ek,j+1 = x ^ ek+1,j = y ^ ek+1,j+1 = q ^

^ ek,j+2 = ek+1,j+2 ^ … ^ ek,N = ek+1,N

para algún valor de j. A esta fórmula la denotaremos k,j,p,q,x,y,+ o también k,j,T, donde T denota la transición usada.

Teorema de Cook, XI

• Como consecuencia de lo anterior, la fórmula proposicional que represente a la afirmación 2)

0,T0 0,0,T0 v 0,1,T0 v … v 0,N,T0

representa que la transición T0 se aplique en el primer estado. Se pueden definir análogamente las fórmulas j,T para j y T arbitrarios.

Teorema de Cook, XII

• De nuevo como consecuencia de lo anterior, la fórmula lógica

= (0,T0 v 0,T1 v … v 0,Ts) ^

^ (1,T0 v 1,T1 v … v 1,Ts) ^

^ … ^

^ (N,T0 v N,T1 v … v N,Ts)

representa la afirmación 2).

Teorema de Cook, XIII

• Hay una máquina de Turing que puede construir la fórmula v v , lo que demuestra que el problema de aceptación por una máquina de Turing indeterminista con complejidad indeterminista polinomial se reduce al problema SAT, y por lo tanto, que éste es un problema NP, terminando la demostración del Teorema de Cook.

Reducciones polinomiales de problemas NP-completos

• Si un problema NP-completo tiene una re-ducción polinomial a otro problema, enton-ces el segundo también es NP-completo.

• Demostración: Cualquier otro problema NP se puede reducir al primero mediante un algoritmo polinomial. La composición de este algoritmo con el que reduce el primer problema al segundo es otro algoritmo que reduce el tercer problema al segundo.

Otros problemas NP-completos

• El problema del viajante es NP-completo.• También lo es el problema CSAT, pues SAT

se reduce a él polinomialmente• El problema de hallar un subgrafo de otro

dado de modo que toda arista del inicial tenga uno de sus vértices en uno de los vértices del subgrafo es otro problema NP completo

• Hoy en día se conocen centenares de problemas NP-completos

El problema P-NP

• Los dos problemas abiertos más famosos en Matemáticas y Computación Teórica son la conjetura de Riemann (relacionada con las propiedades asintóticas del conjunto de los números primos) y el problema P-NP, consistente en determinar si P=NP o no.

El problema P-NP, II

• Para demostrar que P=NP basta con demostrar que algún problema NP completo es P. En particular, basta con encontrar un algoritmo con complejidad polinomial que resuelva el problema SAT o NSAT (aparentemente más sencillo), el problema del viajante o cualquiera de los otros cientos de problemas NP-completos conocidos.

• Sin embargo, hasta ahora nadie ha encontrado un algoritmo de ese tipo. Muchos expertos piensan que no lo hay, pero no saben cómo demostrarlo.