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 x0 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) On Setembro 2004 2 log2 n maxcij • logn logcmax Cn 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? APĀ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. AP…Ā? 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