Parte 4 Teoria da complexidade. Setembro 2004Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro2 Motivação : –problema x algoritmo –classificação

Parte 4

Teoria da complexidade

Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 2

• 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}



• 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



• Caixeiro viajante – S: n– Q: matriz cij

– Af: verifica se f é um ciclo hamiltoniano– Ac: cálculo do custo de um ciclo

• Clique de cardinalidade máxima– 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 x0– Ac: cálculo de c·x


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.


• 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



• Hipotése:

O custo Z* de uma solução ótima é um número inteiro cujo logaritmo é limitado por um polinômio

• Então:

algoritmo PD algoritmo PA

• 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


MIN

MAX


• 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)?

Exemplo: 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

adjacentesretornar {v} MAXCLIQUE(G(v)-v)

fim MAXCLIQUE

cliquesize(G) = cliquesize(G(v)) ↔ v clique máxima


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))


• PD PO: algoritmo TSPDEC(n,c,L) para problema de decisão

2,, UBLBcn

procedure TSPOPTLB ← 0UB ← n·max{cij}enquanto UB ≠ LB faça

se TSPDEC = “sim” entãoUB ←

senãoLB ←

OPT ← UBpara 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

2/UBLB 2/)(,, UBLBcn

12/ UBLB

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)

ijcn maxlog2

1010

nCcnnO max2 loglog

Exemplo: TSP


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


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)


Classe 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)

P NP P = NP ? P NP?


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, L2ou– 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!


Classe NP

• Exemplo: existe x {0,1}n satisfazendo A·x b?

para j = 1 até n faça go to both L1, L2

L1: xj ← 0 go to L3

L2: xj ← 1L3: continue

se A·x b então “SIM”

senão “NÃO”

Ax b?

x1=0 x1=1

x2=0 x2=1 x2=1x2=0

... ...

...

não sim não sim


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


Reduções polinomiais

: 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

BA R

BA

BA

BA

R

R

R

alg. pol. B algoritmo polinomial para A

algoritmo polinomial para B alg. pol. A

alg. pol. B???


Transformações polinomiais

: 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.

BA T


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: simL=3: não

• Coloração: existe uma coloração utilizando no máximo L cores ?

L=4: simL=3: não


• 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?

• Ciclo hamiltoniano: o grafo possui um ciclo hamiltoniano?

Exemplos: problemas

L=2: simL=3: não

Não existe algoritmo polinomial conhecido: não há ou não se conhece?


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

• G tem um ciclo hamiltoniano se e somente se existe um ciclo visitando todos os nós de G’ com comprimento igual a n

construir um grafo G’=(V’, E’) com V’=Vn ← |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)


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.


Conjunto independente e cobertura por vértices

VC

CI

VC(G,k) G’ ← Gk’ ← |V| - k

retornar a resposta de IS(G’,k’)


Clique

• Dado um grafo G=(V,E) e um inteiro j |V|, existe uma clique formada por j vértices?

2424

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)

VC IS clique1

2 3

5

6

4

1

2 3

5

6

4

G’= grafo complementar de G


Problemas NP-completos

• Um problema A é NP-completo se:1) A NP2 B NP,

• Problemas de decisão apenas!• Em geral, mostrar que um outro problema NP-completo C é tal

que • É necessário mostrar que um (primeiro) problema é NP-

completo

AB T

AC T


Problema de satisfabilidade (SAT)

• Cook 1971: Problema de satisfatibilidade SAT é NP-completoEntrada: expressão booleana na forma normal conjuntivaSaída: esta expressão pode ser satisfeita? (SIM/NÃO)

?1:1,0,, 3

321

231323112

Exxx

xxxxxxxxxE

• 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.


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 2. Demonstrar que B NP–completo tal que ou que

B é caso particular de A

• Base de todas as provas de NP-completude: o problema SAT é NP-completo.

AB T


Teorema: 3-SAT é NP

• 3-SAT: cada cláusula tem exatamente 3 literais

• Ci: 3 literais

• Ci: 2 literais

• Ci: 1 literal

SATSAT

NPSATT 3

3

2828

542152342321 xxxxxxxxxxxx

xxxx 21212121

aaaa

babababa

+ ↔ · ↔


Teorema: 3-SAT é NP

• Ci: + 3 literais

2929

completoNPéSAT

satisfeitaécsatisfeitaéc

cc

c

xxfazer

c

xxxxxxc

kc

ii

iji

i

jj

ji

kkki

ki

3

'

011'

1'

0

11

'

3

12

13342231121

21


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-completo2. 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)

3030

T


0 0 0 d

0 1 1 d

1 0 0 d

0 d 0 0

0 d 1 0

1 d 0 0

0 d 1 1

0 0 0 d

0 0 1 d

0 1 0 d

d 0 0 0

d 0 0 1

d 1 0 0

1 1 1 d d 1 1 1

0 0 1 d 0 d 0 1

1 0 0 d

d 1 0 1

1 1 0 d

d 0 1 1

1 0 1 d

1 d 1 0 1 1 0 d d 1 1 0

1 1 1 d 1 d 1 1

1 0 1 d

432321431321 xxxxxxxxxxxx

0 0 0 d 0 d 0 0 0 0 0 d d 0 0 0

0 0 1 d d 0 0 1 0 0 1 d 0 d 0 1

1 0 0 d 1 d 0 0 d 1 0 0 1 0 0 d

1 1 0 d 1 d 1 0 1 1 0 d d 1 1 0

0 d 1 1 d 1 0 1 1 0 1 d 1 0 1 d

d 0 1 1 0 1 1 d 0 d 1 0 0 1 0 d

1 1 1 d d 1 1 1 1 1 1 d 1 d 1 1

d 0 1 1

1 0 1 d

1 d 1 1

1 0 1 d

3131



• atribuição parcial de valores

• 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

3232

ddxxxx

014321



• | clique | = m um nó por coluna– APVs compatíveis– 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 clique

• Clique é NP-completo

dd

xxxx

014321

3333

T


Clique é NP-completo

• 3-SAT clique• cada literal em F nó de G • arestas de G: pares de literais podem receber o valor 1

simultaneamente

FG=[N, A]N={(x, i): x é literal na cláusula i}A={[(x,i), (y, j)] : x ≠ y, x ≠ y, i ≠ j }

T

3434


Clique é NP-completo

33211 xxxxxF

3535

( x3, 2) (x1, 1) (x3, 3) ( x1, 2)

(x2, 2)


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 ?

3636


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ção1. hamiltoniano circuito NP-completo2. 3-SAT hamiltoniano circuito

• dado uma fórmula booleana F consistindo de m cláusulas C1, …Cm e envolvendo n variáveis x1,…xn

3737

T


TSP é NP-completo ?

3838

u’u

v v’

z1 z2 z3 z4

u’u

v v’

u’u

v v’

u’u

v v’

A



3939

u1

u2

u3

u4

u1

u2

u3

u4



4040

u1

u2

u3

u4

u1

u2

u3

u4

u1

u2

u3

u4

B


321321321 xxxxxxxxxF

B

B

B

A

A

A

A

A

A

A

A

A

Este circuitohamiltonianocorresponde a:t(x1)=truet(x2)=falset(x3)=false


TSP é NP-completo

• parte 2 da demonstração– hamiltoniano circuito 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.

T

4242


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.

4343

A P … Ā ?Certificado para instâncias SIM!


Co-NP

4444

• 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


Co-NP

NP

4545

Co-NP

NP-completo Co-NP-completo

CHTSP

CHTSP

P=NP?NP=co-NP?


Problemas NP-difíceis

• A é NP-difícil se B NP, 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 PSPACENP PSPACEP = PSPACE P = NPP = PSPACE P = NP

4646

X

AB R


Classes de problemas

CoNP

4747

P

complementos

NP-Completos NP-Completos

NP


PSPACE

4848

PSPACE-completos PSPACE

CoNP

P

complementos

NP-Completos NP-Completos

NP


PSPACE

4949

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


Algoritmos pseudopolinomiais

5050

• 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 NP-completo 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

Documents

Parte 4 Teoria da complexidade. Setembro 2004Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro2 Motivação : –problema x algoritmo –classificação