casa de moonticulo

Complejidad - Problemas NP-Completos

Algoritmos y Estructuras de Datos III

La teor´ de NP-completitud
ıa

Un algoritmo eficiente es un algoritmo de complejidad
polinomial.
Un problema est´ bien resuelto si se conocen algoritmos
a
eficientes para resolverlo.
El objetivo es clasificar los problemas seg´n su complejidad.
u
Se aplica a problemas de decisi´n, o sea problemas que toman
ociertos par´metros y tienen como respuesta SI o NO (aunque
a
es sencillo ver que sus implicancias pueden extenderse a
problemas de optimizaci´n).
o

La teor´ de NP-completitud
ıa

Una instancia de un problema es una especificaci´n de sus
o
par´metros. Un problema de decisi´n π tiene asociado un
a
o
conjunto Dπ de instancias y un subconjunto Yπ ⊆ Dπ de
instancias cuya respuesta esSI.

Ejemplo: TSP
Dado un grafo completo con peso en las aristas y un n´mero k,
u
¿existe un circuito Hamiltoniano de longitud a lo sumo k?

1

1
2

1

1
1

k=2

1
1

1
2
1
1

1
2
1
1

4

k=6

1

k=4

Distintas versiones de un problema de optimizaci´n π
o
Dada una instancia I del problema π:
Versi´n de evaluaci´n: Determinar el valor de una soluci´n
oo
o
o
´ptima de π para I .
Versi´n de optimizaci´n: Encontrar una soluci´n ´ptima del
o
o
o o
problema π para I (de valor m´
ınimo o m´ximo).
a
Versi´n de decisi´n: Dado un n´mero k, ¿existe una soluci´n
o
o
u
o
factible de π para I tal que c(S) ≤ k si el problema es de
minimizaci´n (o c(S) ≥ k si el problema es de
o
maximizaci´n)?
o
Versi´n de localizaci´n: Dado un n´mero k,determinar una
o
o
u
soluci´n factible de π para I tal que c(S) ≤ k.
o

Distintas versiones de un problema de optimizaci´n π
o

¿Qu´ relaci´n hay en la dificultad de resolver las distintas versiones
e
o
de un mismo problema?

Distintas versiones de un problema de optimizaci´n π
o

¿Qu´ relaci´n hay en la dificultad de resolver las distintas versiones
e
o
de un mismo problema?Si resolvemos el problema de decisi´n, podemos resolver el
o
problema de evaluaci´n usando b´squeda binaria sobre el
o
u
par´metro k.
a

Ejemplo: TSP
Dado un grafo completo G con longitudes asignadas a sus aristas:
Versi´n de evaluaci´n: Determinar el valor de una soluci´n
o
o
o
o
´ptima, o sea la longitud de un circuito Hamiltoniano de G de
longitud m´
ınima.
Versi´n deoptimizaci´n: Determinar un circuito Hamiltoniano
o
o
de G de longitud m´
ınima.
Versi´n de decisi´n: Dado un n´mero k, ¿existe un circuito
o
o
u
Hamiltoniano de G de longitud menor o igual a k?
Versi´n de localizaci´n: Dado un n´mero k, determinar un
o
o
u
circuito Hamiltoniano de G de longitud menor o igual a k.

Problemas intratables
Definici´n: Un problema es intratable si no puedeser resuelto por
o
alg´n algoritmo eficiente.
u
Un problema puede ser intratable por distintos motivos:
El problema requiere una repuesta de longitud exponencial
(ejemplo: pedir todos los circuitos Hamiltonianos de longitud
a lo sumo k).
El problema es indecidible (ejemplo: problema de la parada).
El problema es decidible pero no se conocen algoritmos
polinomiales que lo resuelvan.Modelos de Computadoras: DTM
M´quina de Turing Determin´
a
ıstica (DTM)
Consiste de un control finito, una cabeza lecto-escritora y una
cinta con el siguiente esquema.
Control
Cinta

. . .

Cabeza lecto-escritora
. . .

Σ finito, el alfabeto; Γ = Σ ∪ {∗};
Q finito, el conjunto de estados;
q0 ∈ Q, estado inicial; Qf ⊆ Q, estados finales (qsi y qno para
problemas de decisi´n)
oModelos de Computadoras: DTM

Sobre la cinta tengo escrito el input que es un string de
s´
ımbolos de Σ a partir de la celda 1, y el resto de las celdas
tiene ∗ (blancos).
Definimos un programa S como un conjunto de qu´
ıntuplas
S ⊆ Q × Γ × Q × Γ × M, donde M = {+1, −1} son los
movimientos de la cabeza a derecha o izquierda.
Para todo par (qi , sj ), existe exactamente una qu´
ıntupla
que...