Parte 4
Teoria da complexidade
Teoria da complexidade
• Motivação :
–
–
–
–
problema x algoritmo
classificação
Técnicas
Referências básicas: Cook(1971), Karp(1972)
• Problemas de:
– Decisão
– Avaliação
– Otimização
• Problema  {instâncias}
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
2
Teoria da complexidade
• Instância: par {F,c}
– F = {soluções viáveis}
– função de custo c: F  R
• F e c são dados implicitamente atraves de dois algoritmos
• Algoritmo Af: dados objeto f e conjunto S de parâmetros,
determinar se f  F
• Algoritmo Ac: dados solução viável f e conjunto Q de
parâmetros, calcular c(f)
• Instância: representação dos parâmetros S e Q
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
3
Teoria da complexidade
•
Caixeiro viajante
–
–
–
–
•
Clique de cardinalidade máxima
–
–
–
–
•
S: n
Q: matriz cij
Af: verifica se f é um ciclo hamiltoniano
Ac: cálculo do custo de um ciclo
S: G
Q: Ø
Af: verifica se f é uma cique
Ac: cálculo de |f|
Programação linear
–
–
–
–
S: A,b
Q: c
Af: verifica se A·x=b e x0
Ac: cálculo de c·x
Setembro 2004
Problema de otimização:
Dadas as representações dos
conjuntos S e Q para os
algoritmos Af e Ac, obter a
solução viável ótima.
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
4
Teoria da complexidade
• Problema de otimização
– dados S e Q, obter a solução ótima
• Problema de avaliação
– dados S e Q, obter o custo da solução ótima
• Problema de decisão
– dados S e Q, assim como um inteiro L, existe uma solução viável f
tal que c(f)  L? (pergunta que espera uma resposta sim ou não)
• Toda a teoria da complexidade se baseia nos problemas de
decisão.
• PD não é mais difícil do que PA
• PA não é mais difícil do que PO
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
5
Teoria da complexidade
•
Hipotése:
O custo Z* de uma solução ótima é um número inteiro cujo
logaritmo é limitado por um polinômio
•
MIN
Então:
algoritmo PD  algoritmo PA
MAX
•
Pesquisa binária no intervalo [O, Z*]
log Z* iterações = O(P(L))
PD polinomial  PA polinomial
PA  PO não existe regra geral
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
6
Exemplo: clique máxima
•
•
•
Dado um grafo, obter uma clique de cardinalidade máxima
PA: existe algoritmo cliquesize(G) de complexidade C(n)
Algoritmo MAXCLIQUE para PO? Complexidade T(n)?
cliquesize(G) = cliquesize(G(v)) ↔ v clique máxima
procedure MAXCLIQUE(G)
se |G| = 0 então
retornar Ø
senão seja um nó v tal que
cliquesize(G) ← cliquesize(G(v)), onde G(v) é o subgrafo
de G formado por v e todos os nós a ele adjacentes
retornar {v}  MAXCLIQUE(G(v)-v)
fim MAXCLIQUE
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
7
Exemplo: clique máxima
T(0) = O(1)
T(n) = (n+1) · C(n) + T(n-1) + O(n)
T(n) = [(n+1)+n+...+1] . C(n) + [O(n)+O(n-1)+...+O(1)]
T(n)=O(n2 · C(n))
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
8
Exemplo: TSP
•
PD  PO: algoritmo TSPDEC(n,c,L) para problema de decisão
procedure TSPOPT
LB ← 0

 LB  UB  
 n, c, 
 
2



UB ← n·max{cij}
enquanto UB ≠ LB faça
n, c, (LB  UB) / 2 = “sim” então
se TSPDEC


UB ←  LB  UB / 2
senão
LB UB / 2  1
LB ←
OPT ← UB
para i = 1 até n faça
para j = 1 até n faça
tmp ← cij
cij ← 
se TSPDEC(n, c, OPT) = “não” então cij ← tmp
fim TSPOPT
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
9
Exemplo: TSP
Número de iterações da busca binária:
•
Número de iterações da segunda fase: n2
•
C(n) = complexidade de TSPDEC(n,c,L)
On
Setembro 2004
2


log2 n  maxcij 
•


 logn  logcmax  Cn
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
10
10
Classe P
• Problemas de decisão: resposta Sim ou Não
• Classe P: classe de problemas de decisão para os quais são
conhecidos algoritmos polinomiais
• Exemplos (problemas de decisão):
–
–
–
–
Caminho mais curto
Árvore de peso mínimo
Determinar se um grafo é planar
Programação linear
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
11
Classe NP
• Classe NP (definição 1): o problema de decisão A pertence à
classe NP se existe um algoritmo polinomial Af tal que qualquer
que seja uma instância “sim” de A, então existe um objeto
(certificado, proposta de solução) de tamanho polinomial que
leva a resposta “sim” pela aplicação do algoritmo Af.
– Clique: {lista de nós candidatos}
– TSP: {permutação de n objetos}
– PL 0/1: {lista de variáveis=1}
• A definição não se preocupa com a forma pela qual o
certificado é construído (certificado fornecido por um oráculo)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
12
Classe NP
P  NP
P = NP ?
P  NP?
• O processo de “justificar” uma resposta (SIM/NÃO) a um
problema de decisão pode ser decomposto em duas etapas:
– Fornecer uma justificativa (certificado, proposta)
– Verificar se a justificativa é satisfatória
– Exemplo: TSP
• SIM  ciclo H de comprimento  L
• NÃO  lista de todos ciclos (>L)
• Classe NP: etapa de verificação das respostas “sim” pode ser
feita em tempo polinomial
algoritmo + entrada
(problema+certificado)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
13
Classe NP
• Classe NP (definição 2): o problema de decisão A pertence à
classe NP se existe um algoritmo não-determinístico polinomial
para sua solução
• Algoritmo não-determinístico: todas as instruções, mais
– go to both L1, L2
ou
– escolha (a, b)
• Cálculos em paralelo:
– O número de ramos pode crescer exponencialmente
– Se um ramo leva à resposta “sim”: SIM
– Se todos os ramos levam à resposta “não”: NÃO
Ferramenta irrealista, teórica, ...
...mas poderosa!
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
14
Classe NP
• Exemplo: existe x  {0,1}n satisfazendo A·x  b?
L1:
L2:
L3:
para j = 1 até n faça
go to both L1, L2
xj ← 0
go to L3
xj ← 1
continue
se A·x  b então
“SIM”
senão
“NÃO”
Setembro 2004
x1=0
x1=1
x2=0 x2=1 x2=0
...
x2=1
...
...
não sim
não sim
Ax  b?
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
15
Classe NP
• Instâncias “SIM”: certificado polinomial (um ramo)
• Instâncias “NÃO”: podem não ter certificado polinomial (todos
ramos)
• Um algoritmo não-determinístico é polinomial se:
– ele resolve o problema e
– o número de operações realizados pela primeiro ramo a
levar à resposta “SIM” é polinomial
• Analogia com a propriedade de certificado sucinto: instâncias
“SIM” têm um certificado sucinto, instâncias “NÃO” podem não
ter
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
16
Reduções polinomiais
R
A

B : O problema A se reduz polinomialmente ao
problema B se existe um algoritmo para resolver A que utiliza
um número polinomial de vezes um algoritmo para resolver B
R
A

B   algoritmo polinomial para A
 alg. pol. B
R
A

B   algoritmo polinomial para B
 alg. pol. A
R
A

B  ???
 alg. pol. B
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
17
Transformações polinomiais
T
A

B: O problema A se transforma polinomialmente no
problema B se existe um algoritmo polinomial para construir
uma instância de B a partir de cada instância de A, de tal modo
que se a instância de A leva a uma resposta “SIM” para A,
então a instância transformada de B leva a uma resposta “sim”
para B.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
18
Exemplos: problemas
• Existe uma clique de cardinalidade maior ou igual a L?
• Recobrimento por nós: existe um recobrimento por nós das
arestas do grafo com cardinalidade menor ou igual a L?
L=4: sim
L=3: não
• Coloração: existe uma coloração utilizando no máximo L cores ?
L=4: sim
L=3: não
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
19
Exemplos: problemas
• Caixeiro viajante: existe um ciclo hamiltoniano de comprimento
menor ou igual a L?
• Conjunto estável: existe um subconjunto estável de
cardinalidade maior ou igual a L?
L=2: sim
L=3: não
• Ciclo hamiltoniano: o grafo possui um ciclo hamiltoniano?
Não existe algoritmo polinomial conhecido: não há ou não se conhece?
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
20
Ciclo hamiltoniano
• CH: dado um grafo G=(V,E), existe um ciclo (hamiltoniano) que
visita cada um de seus vértices exatamente uma vez?
• CH  TSP
construir um grafo G’=(V’, E’) com V’=V
n ← |V|
para i = 1 até n faça
para j = 1 até n faça
se (i, j)  E então
w(i, j) ← 1
senão
w(i, j) ← 2
retornar resposta de TSP(G’, n)
• G tem um ciclo hamiltoniano se e somente se existe um ciclo
visitando todos os nós de G’ com comprimento igual a n
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
21
Conjunto independente e cobertura por vértices
• VC (cobertura por vértices): dados um grafo G=(V,E) e um inteiro k
 |V|, existe um subconjunto S  V com no máximo k vértices tais
que qualquer aresta de E tem pelo menos uma extremidade em S?
• Cobertura trivial: S=V
• Conjunto de nós S é independente  qualquer par de nós i,j  S,
nao existe arco (i, j)  E
• IS (conjunto independente): dados um grafo G=(V,E) e um inteiro k
 |V|, existe um subconjunto independente formado por k nós?
• Se S é uma cobertura por vértices, então V-S é um conjunto
independente
Prova: suponha que V-S não seja um conjunto independente, ou
seja, existe um arco com ambas extremidades em V-S. Então,
neste caso, S não seria uma cobertura.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
22
Conjunto independente e cobertura por vértices
VC
CI
VC(G,k)
G’ ← G
k’ ← |V| - k
retornar a resposta de IS(G’,k’)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
23
Clique
• Dado um grafo G=(V,E) e um inteiro j  |V|, existe uma clique
formada por j vértices?
G’= grafo complementar de G
IS(G,k)
construir G’=(V’, E’) com V’=V e
 (x, y)  E então (x, y) E’
retornar a resposta de clique(G’,k)
1
1
VC  IS  clique
2
3
2
6
6
5
Setembro 2004
3
4
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
5
4
24
24
Problemas NP-completos
• Um problema A é NP-completo se:
1) A  NP
 A
2)  B NP, B 
T
• Problemas de decisão apenas!
• Em geral, mostrar que um outro problema NP-completo C é tal
T
que C 

A
• É necessário mostrar que um (primeiro) problema é NPcompleto
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
25
Problema de satisfabilidade (SAT)
• Cook 1971: Problema de satisfatibilidade SAT é NP-completo
Entrada: expressão booleana na forma normal conjuntiva
Saída: esta expressão pode ser satisfeita? (SIM/NÃO)

 


E  x2  x1  x1  x3  x2   x3   x1  x3  x2

  x1 , x2 , x3   0,1 : E  1?
3
• Idéia da demonstração: mostrar que qualquer problema que
pode ser resolvido por um algoritmo não-determinístico
polinomial equivale a determinar se uma expressão booleana
pode ser satisfeita.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
26
Classe NP
• Classe NP (definição 3): Um problema de decisão A pertence à
classe NP se pode ser transformado em tempo polinomial em
um problema de programação inteira
• Demonstrar que A é NP- completo:
1. Demonstarr que A  NP
T
2. Demonstrar que  B NP–completo tal que B 

A
B é caso particular de A
ou que
• Base de todas as provas de NP-completude: o problema SAT é
NP-completo.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
27
Teorema: 3-SAT é NP
+ ↔
· ↔
• 3-SAT: cada cláusula tem exatamente 3 literais
3  SAT  NP

T
SAT 

3  SAT
• Ci: 3 literais

 
 

x1  x2  x3  x2  x4  x3  x2  x5  x1  x2  x4  x5 
• Ci: 2 literais
1  2   1  2  x  x  1  2  x 1  2  x
• Ci: 1 literal


 

    a  b     a  b    a  b    a  b
    a  a    a     a

Setembro 2004


Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
28
28
Teorema: 3-SAT é NP
• Ci: + 3 literais
ci  1  2    k  k  3





c'i  1  2  x1   x1  3  x2  x2  4  x3    x k 3  k 1  k

ci  1   j  1
fazer x j  2  x j 1  0
 c'i  1
c'i  1   j  1  ci  0
ci é satisfeita  c'i é satisfeita
 3  SAT é NP  com pleto
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
29
29
Clique é NP-completo?
• dados um grafo G e um inteiro L, G tem uma clique com  L
nós?
• Clique  NP-completo
• demonstração
1. Clique  NP-completo
T
2. 3-SAT 
clique

• associar a cada expressão booleana F com 3 literais por
cláusula um grafo G (m cláusulas, n variáveis)
• mostrar que G tem uma clique de cardinalidade k  F pode
ser satisfeita (k=m)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
30
30
x  x
1
2



 x3  x1  x3  x4  x1  x2  x3  x2  x3  x4
000d
0d00
000d
d000
001d
0d01
001d
d001
011d
0d10
010d
d011
100d
1d00
100d
d100
101d
0d11
101d
d101
110d
1d10
110d
d110
111d
1d11
111d
d111
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro

31
31
Clique é NP-completo?
• atribuição parcial de valores
x1 x2
1 d
x3
0
x4
d
• compatibilidade entre duas APVs
(1
d
0 d)  (d
1
0 1)
• V: 7 nós por cláusulas
(APVs viáveis =1)
• arestas: APVs compatíveis
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
32
32
Clique é NP-completo?
• | clique | = m  um nó por coluna x1
– APVs compatíveis
1
x2
x3
d
0
x4
d
– provém da mesma atribuição completa de t
– atribuição completa t satisfaz todas as cláusulas (porque a única
que não leva a um valor =1 é omitida)
– F=1
• F=1  cada restrição de t às variáveis de cada cláusula é um
nó da coluna  compatíveis 2 a 2  | clique | = m
• 3-SAT
T
clique


• Clique é NP-completo
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
33
33
Clique é NP-completo
• 3-SAT
T


clique
• cada literal em F nó de G
• arestas de G: pares de literais podem receber o valor 1
simultaneamente
F
G=[N, A]
N={(x, i): x é literal na cláusula i}
A={[(x,i), (y, j)] : x ≠ y,  x ≠ y, i ≠ j }
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
34
34
Clique é NP-completo


F  x1   x1  x2  x3  x3 
(x2, 2)
( x3, 2)
Setembro 2004
(x1, 1)
(x3, 3)
( x1, 2)
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
35
35
TSP é NP-completo?
• dados um grafo G(V,E) e um inteiro L=|V|, constrói-se uma
instância de |V| cidades tomando-se dij=1 se [vi, vj]  E, caso
contrário 2.
• existe um tour de tamanho L ou menor  existe um circuito
hamiltoniano em G
• TSP  NP-completo ?
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
36
36
TSP é NP-completo?
• demonstrar que se pode construir um grafo G=(V, E) tal que G
tem um circuito hamiltoniano  F é satisfatível.
• parte 1 da demonstração
1. hamiltoniano circuito  NP-completo
2. 3-SAT
T
hamiltoniano circuito


• dado uma fórmula booleana F consistindo de m cláusulas
C1, …Cm e envolvendo n variáveis x1,…xn
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
37
37
TSP é NP-completo ?
u’
u
z1
z2
z3
u’
u
A
z4
v
v’
v
v’
u
u’
u
u’
v
v’
v
v’
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
38
38
TSP é NP-completo ?
Setembro 2004
u1
u1
u2
u2
u3
u3
u4
u4
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
39
39
TSP é NP-completo ?
u1
u1
u1
u2
u2
u2
B
Setembro 2004
u3
u3
u3
u4
u4
u4
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
40
40



F  x1  x2  x3  x1  x2  x3  x1  x2  x3
B

A
A
A
A
A
B
A
Este circuito
hamiltoniano
corresponde a:
t(x1)=true
t(x2)=false
t(x3)=false
A
A
A
B
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
41
41
TSP é NP-completo
• parte 2 da demonstração
– hamiltoniano circuito
T


3-SAT
• arestas [uij, ui, j+1] para alguma cláusula Ci são utilizadas no
circuito hamiltoniano  a correspondente [vk, wk] não é
utilizado. Ou seja, o correspondente literal é falso.
• logo, como fazem parte do grafo B, nem todas as árvores são
utilizadas no circuito hamiltoniano. Equivalentemente,
a
correspondente cláusula Ci é satisfeita. Como isto ocorre em
todas as cláusulas, todas elas são satisfeitas e F é satisfatível.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
42
42
Co-NP
• CH: Dado um grafo G, G é não hamiltoniano?
• CH  NP? Certificado?
• o problema Ā é o complemento de A se o conjunto de
ocorrências que levam a uma resposta SIM para Ā levam à
resposta NÃO para A
• TSP: n, D=(dij), L todo ciclo hamiltoniano tem comprimento > L?
• A: dado um grafo G, G é conexo?
• Ā: dado um grafo G, G não é conexo?
APĀP
• demonstração: A  P   algoritmo polinomial para resolver A
 um algoritmo polinomial para Ā pode ser obtido, com a
resposta NÃO onde o primeiro respondia SIM.
AP…Ā?
Certificado para instâncias SIM!
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
43
43
Co-NP
• classe dos problemas cujo complemento NP
• Teorema: Se o complemento de um problema NP-completo
NP, então NP=co-NP
• de todos os problemas em NP, os NP-completos são
aqueles cujos complementos menos provavelmente pertencem
a NP. Inversamente, se o complemento de um problema de um
problema de NP também pertencem a NP, isto é evidência de
que este problema não é NP-completo
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
44
44
Co-NP
P=NP?
NP=co-NP?
Co-NP
NP
CH
TSP
NP-completo
Setembro 2004
CH
TSP
Co-NP-completo
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
45
45
Problemas NP-difíceis
R
• A é NP-difícil se  B  NP, B 

A e A não é demonstrado
como pertencente a NP
• A é a versão “otimização” de um problema NP-completo
• PSPACE: classe de problemas que podem ser resolvidos em
espaço limitado por um polinômio
P  PSPACE
NP  PSPACE
P = PSPACE  P = NP
P = PSPACE 
X P = NP
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
46
46
Classes de problemas
CoNP
NP
P
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
47
47
PSPACE
PSPACE-completos
CoNP
PSPACE
NP
P
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
48
48
PSPACE
A é NP-completo. E daí ?
1. algoritmos aproximativos
2. algoritmos probabilísticos
3. casos especiais
4. heurísticas
5. busca local
6. Algoritmos exatos não-polinomiais
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
49
49
Algoritmos pseudopolinomiais
•
•
•
•
L : tamanho do problema
L’: maior inteiro na instância
Complexidade é O(P(L, L’))
Exemplo: KS O(b n)
Um problema é fortemente NP-completo se ele continua NPcompleto mesmo se restrito a L’=P(L) para um certo polinômio P.
Ex. 1: clique L’ = k  n=P(n)
Ex. 2: TSP continua NP-completo mesmo se dij  n
Ex. 3: KS b  n  O(n2) não é fortemente NP-completo
Teorema: exceto P=NP, algoritmo pseudopolinomial para os
problema fortemente NP-completos
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
50
50