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 proposicionales 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:
– x i = r 1 v xi = r 2 v … v x i = r n
– xi = xj  xj = x i
– 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
(p1p2…pn)(q1q2…qm)
es satisfactible si y sólo si
(p1X)(p2X)…(pnX)
(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 problemas
1. 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 elecciones consecutivas de transiciones y tambié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 reducción polinomial a otro problema, entonces 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.
Descargar

Diapositiva 1