Análise de Algoritmos

Ronaldo Cristiano Prati

Bloco A, sala 513-2

ronaldo.prati@ufabc.edu.br

Tipos de problemas

  • Problema de decisão, em que a resposta é sim ou não
  • Problema de busca, em que queremos encontrar uma solução satisfazendo algumas propriedades se ela existir. Caso contrário, retornar que não exite
  • Problema de otimização, em que cada solução tem um valor associado, e queremos encontrar uma solução com o melhor valor (máximo ou mínimo)

Tratabilidade

  • Intuição:

    • Problema é tratável se existem algoritmos eficientes para ele
    • Problema é intratável se tais algoritmos não existem
  • Até agora no curso, praticamente todos os problemas que encaramos eram tratáveis

  • Mas nada garante que seja sempre este o caso

Algoritmo eficiente

  • Definição clássica de eficiência:

    • Um algoritmo é eficiente se e somente se ele executa em tempo polinomial em um computador serial
  • Se o grau do polinômio for grande, o problema deve ser inviável

    • O(n)O(n), O(nlogn)O(n \log n), O(n2log2n)O(n^2 \log^2 n) - ok!
    • O(n10.000.000.000)O(n^{10.000.000.000}) - eficiente?
  • Tempo de execução exponencial podem ser eficientes na prática

    • O(2n)O(2^n), O(n!)O(n!) - ok!
    • O(1.0000000001n)O(1.0000000001^n) - ineficiente?

Tratabilidade

  • Um problema é chamado de tratável se e somente se existe um algoritmo eficiente (isto é, de tempo polinomai) que o revolsa.

  • Um problema é chamado de intratável se e somente se não existe um algoritmo eficiente que o resolva.

  • Problemas intratáveis são comuns. Precisamos reconhecê-los quando nos deparamos com algum deles na prática.

A classe de complexidade P

  • P é a classe dos problemas resolvidos em tempo polinomial
  • Exemplos de problemas em P:
    • Caminho mais curto
    • Ordenação
    • Árvore geradora mínima
    • Fluxo em redes
    • Multiplicação de matrizes

A classe de complexidade P

  • Infelizmente, nem todo problema está em P 😦
  • Existem problemas para os quais não existe qualquer algoritmo
    Ex. problema da Parada
  • Existem outros para os quais, por mais que se busque, não sãoconhecidos algoritmos polinomiais
    Ex.: problema do Caixeiro Viajante (TSP)
  • Mas, a princípio, isso não garante que tais algoritmos não existam
  • Como descrever uma classe que englobe problemas como o TSP?

A classe de complexidade NP

  • A classe NP consiste em todos os problemas de decisão em que podemos verificar se uma solução é correta em tempo polinomial

  • Essas definições são algorítmicas

  • Definiçõeses formais destas classes vem da área de teoria da computação

  • O nome NP significa "Nondeterministic Polynomial"

A classe de complexidade NP

  • Todo problema em NP é resolvével usando busca por força bruta

    • O espaço de busca é no máximo exponencial, e cada solução pode ser testada em tempo polinomal
  • Exemplos:

    • Satisfatibilidade (SAT)
    • Cobertura por Vértices
    • Problema do Caixeiro Viajante (TSP)

P e NP

  • Situação dos problemas

    • Temos problemas em P, que também estão em NP (por que?)
    • Temos problemas em NP, que não sabemos se estão em P
  • Muitos problemas importantes na segunda situação

  • Como corroborar a dificuldade destes problemas?

    • Vamos utilizar evidências relativas, usando:
      • Redução
      • Completude

Redução

  • O problema AA se reduz ao problema BB se conseguimos resolver qualquer instância de AA usando um algoritmo que resolve BB
  • Transformamos a entrada AA em entrada BB, e depois a solução BB em solução AA
  • Se transformações são polinomiais, AA é polinomialmente redutível a BB

Redução

  • Exemplo: Seleção em Ordenação. Vamos usar um algoritmo de ordenação para selecionar o kk-ésimo menor elemento de de um vetor
  • Esta reduçãoo resolve o problema da seleção em tempo O(nlogn)O(n \log n)
  • Note que é possível resolver a seleção em tempo linear

Redução

  • Numa redução o algoritmo para BB pode ser utilizado várias vezes
  • Exemplo: Caminho Todos para Todos em Caminho Um para Todos
  • Notem que nesse caso o algoritmo obtido ainda é polinomial

Redução

  • Reduçãoo entre problemas é uma técnica valiosa para o projeto de algoritmos
  • Permite utilizar soluções já conhecidas para resolver novos problemas
  • Um projetista de algoritmos sempre deve se perguntar:

“Será que este problema não se parece com algum que eu já conheço?”

Redução

  • Redução usada para atestar a dificuldade relativa de um problema
  • Como provar que um problema é tão difícil quanto outro?
  • Observe que BB não pode ser mais fácil do que A

Clique-k

  • Dados um grafo GG e um inteiro positivo kk, existe conjunto SV(G)S\subseteq V(G) de vértices tais que para todo par u,vSu,v \in S existe uma aresta uvE(G)uv \in E(G) (S é clique) e Sk|S|\geq k?
  • Clique-k está em NP:
    • É um problema de decisão (a resposta é sim caso exista)
    • Dados GG, kk e SS É fácil verificar se SS é uma clique: basta verificar se todos os pares de vértices formam arestas e contar os vértices de SS

kk-Cobertura por vértices

  • Dado um grafo GG e um inteiro kk, existe conjunto SV(G)S\subseteq V(G) tal que, para toda aresta uvE(G)uv \in E(G), uSu \in S ou vSv \in S e Sk|S|\leq k?
  • kk-Cobertura por vértices está em NP pois, dados GG, kk, e SS podemos verificar em tempo polinomial se Sk|S|\leq k e se todas as arestas do grafo tem ao menos uma aresta no conjunto.

Redução

  • Exemplo: Clique-k é redutivel para k-cobertura por vértices
  • Se clique-k não tiver um algoritmo polinomial
  • Então k-cobertura por vértices também não tem um algoritmo de tempo polinomial

Redução

  • Exemplo: Clique-k é redutivel para k-cobertura por vértices

    • O complemento GcG_c de um grafo GG contém exatamente as arestas que não estão em GG
    • Podemos calcular GcG_c em tempo polinomial
    • GG tem uma clique de tamanho kk se e somente se GcG_c tem uma k-cobertura de tamanho Vk|V|-k

Redução

  • Exemplo: Clique-k é redutivel para k-cobertura por vértices

  • Afirmação: Se GG tem um clique de tamanho kk, GcG_c tem uma k-cobertura de tamanho Vk|V|-k

    • Seja VV' uma clique
    • Então VVV-V' é uma cobertura por vértices em GcG_c
      • Seja (u,v)(u,v) qualquer vértice em GcG_c
      • Então uu e vv não podem estar ambos em VV'
      • E pelo menos uu ou vv está VVV-V', então a aresta (u,v)(u,v) é coberta por VVV-V'
      • Já que isso é valido para qualquer aresta em GcG_c, VVV-V' é uma cobertura por vértices

Redução

  • Exemplo: Clique-k é redutivel para k-cobertura por vértices

  • Afirmação: Se GG tem um clique de tamanho kk, GcG_c tem uma k-cobertura de tamanho Vk|V|-k

    • Para todo u,vVu,v \in V, se (u,v)Gc(u,v) \in G_c, então uVu\in V' ou vVv\in V', ou ambos
    • Caso não fosse verdade, (u,v)E(G)(u,v) \in E(G)
    • Em outras palavras, todos os vértices de VVV-V' estão conectados por uma aresta, então VVV-V' é uma clique
    • Uma vez que VV=k|V|-|V'|=k, o tamanho da clique é kk

Exemplo

  • GG possui uma clique VV' de tamanho kk
  • GcG_c possui uma cobertura por vértice VVV\setminus V' de tamanho nkn-k

Redução

  • Interpretaçõees para “A é redutível a B”:

    • "Positiva" AA ́e no máximo tão difícil quanto BB
    • "Negativa" BB ́e pelo menos tão difícil quanto AA
  • Primeira expande o conjunto de problemas tratáveis

  • Segunda expande o conjunto dos intratáveis

Completude

  • Um Problema Π\Pi é CC-Completo se:

    • Π\Pi está em CC
    • Todo problema em CC é redutível a Π\Pi
  • Podemos pensar que Π\Pi é o "problema mais difícil" em CC

  • Notem quão forte é essa definição

  • E que não é tão óbvio que algum problema Π\Pi em CC a satisfaça

Completude

  • Apesar disso, vamos supor que existam problemas CC-Completos

  • Sendo Π\Pi um problema em CC

  • Para mostrar que Π\Pi ́e CC-Completo temos que:

    • Escolher um problema CC-Completo Π\Pi'
    • Reduzir o problema Π\Pi' para Π\Pi
  • Isso funciona pois:

    • Todo problema em CC é redutível a Π\Pi'
    • E por consequência é redutível a Π\Pi

Completude

  • Voltamos à questão:

    "Como mostrar a dificuldade dos problemas em NP (que não sabemos se estão em P)?”

  • Um forte atestado de dificuldade seria mostrar que todo problema de NPNP reduz pra um desses problemas

  • Já que isso mostraria que esse problema e o mais difícil dentre todosde NPNP e que bastaria resolver ele pra resolver todos os outros

  • Mas, será que a classe dos problemas NP-Completos é ou não vazia?

Completude

  • Por incrível que pareça, existem muitos problemas NPNP-Completos
  • Sendo um exemplo notável o problema da satisfatibilidade (SAT)
  • Já sabemos que para mostrar que um problema é NP-Completo, basta reduzir qualquer problema NPNP-Completo a ele
  • Assim, muitos outros problemas foram provados NPNP-Completos

Satisfatibilidade

  • Considere um conjunto de variáveis booleanas x1,x2,,xnx_1, x_2, \cdots, x_n
  • E uma fórmula composta por essas variáveis e conjunçẽos (operador e) de conjuntos de disjunções (operadores ou). Por exemplo:

(x1x2x3x4)(x1x2)\left(x_{1} \vee \overline{x_{2}} \vee \overline{x_{3}} \vee x_{4}\right) \wedge\left(\overline{x_{1}} \vee x_{2}\right)

(x1x2x3)(x1x2x4x5x6)\left(x_{1} \vee \overline{x_{2}} \vee \overline{x_{3}}\right) \wedge\left(\overline{x_{1}} \vee x_{2} \vee x_{4} \vee x_{5} \vee \overline{x_{6}}\right)

  • Cada conjunto de disjunção é chamado de cláusula.
  • Um literal é uma variável xx ou sua negação x\overline{x}
  • O problema da satisfatibilidade consiste em verificar se a fórmula é satisfatível, isso é, existe uma atribuição de valores para as variáveis tal que a fórmula tem o valor 1.

3-SAT

  • Uma fórmula booleana formada por conjunções de cláusulas que contém exatamente 3 literais é chamado de 3-CNF. Por exemplo

(x1x2x3)(x1x2x4)\left(x_{1} \vee \overline{x_{2}} \vee \overline{x_{3}}\right) \wedge\left(\overline{x_{1}} \vee x_{2} \vee x_{4}\right)
(x1x2x3)(x1x2x4)(x4x5x6)\left(x_{1} \vee \overline{x_{2}} \vee \overline{x_{3}}\right) \wedge\left(\overline{x_{1}} \vee x_{2} \vee x_{4}\right) \wedge\left(\overline{x_{4}} \vee x_{5} \vee \overline{x_{6}}\right)

  • O problema 3-SAT consiste em verificar se uma fórmula 3-CNF é satisfatível, ou seja, se existe uma atribuição de valores para as variáveis tal que a fórmula 3-CNF tenha valor 1.

3-SAT é NP-completo

  • Observe que 3-SAT está em NPNP pois dada uma fórmula e uma atribuição das variáveis, é fácil verificar se essa atribuição satisfaz a fórmula

  • Em 1972, Stepehn Cook e Richard Karp provaram que 3-SAT é NP-completo.

  • Hoje em dia, se conhecem milhares de problemas que são NP-Completos

3-SAT é redutível para Clique-k

  • Dada uma fórmula 3-CNF ϕ\phi com kk cláusulas sobre as variáveis x1,x3,,xnx_1, x3, \cdots, x_n

  • Construímos um grafo GG que possui 3k3k vértices, de modo que cada cláusula tem 3 vértices representando cada um de suas variáveis.

  • Um par de vértices vv e ww de GG forma uma aresta se e somente se vv e ww estão em cláusulas diferentes, vv corresponde a um literal xx
    e ww não corresponde a um literal x\overline{x}

3-SAT é redutível para Clique-k

3-SAT é redutível para Clique-k

  • ϕ\phi com kk clausulas é satisfatível se e somente se existir um clique-k no grafo GG

  • Se existir uma clique em GG, então existe ϕ\phi é satisfatível

    • Por definição, uma clique-k implica que existe kk vértices em GG que são conecatados entre si.
    • Pela nossa construção, o fato que dois vértices estão conectados entre si significa que eles podem receber uma atriuição consistente (podemos atribuir 1 a todos eles), e eles estão em cláusulas diferentes
    • Uma vez que existem kk vértices na clique, então pelo menos uma literal em cada uma das kk cláusulas podem ser atribuídas a 1, isto é, ϕ\phi pode ser satisfeita.

3-SAT é redutível para Clique-k

  • ϕ\phi com kk clausulas é satisfatível se e somente se existir um clique-k no grafo GG

  • Se ϕ\phi pode ser satisfeita, então existe uma clique em GG

    • Se ϕ\phi pode ser satisfeita, então pelo menos uma literal em cada cláusula é atribuída ao valor 1
    • Considere os vértices correspondentes a essas literais. Uma vez que as literais são consistentes e elas estão em diferentes cláusulas, existe uma aresta entre cada par delas.
    • Uma vez que existem kk cláusulas em ϕ\phi, temos um subconjunto de tamanho de pelo menos kk vértices no grafo com arestas entre cada par de vértices, isto é, uma clique-k em G.

NP-Completude

P=?NPP \stackrel{?}{=} NP

  • O problema P=?NPP \stackrel{?}{=} NP é um problema classico

  • Se existir algoritmo polinomial para um problema NP-Completo...

  • conseguimos resolver todos os problemas em NPNP em tempo polinomial, provando que P=NPP=NP...

  • e respondendo assim à maior questão em aberto da ciência da computação.

  • Entretanto, muitos pesquisadores acreditam que isso não é possível, mas não se conhece uma prova que PNPP\neq NP

Problemas NPNP-completos

  • A ligação entre NPNP-Completude e a questão P=?NPP \stackrel{?}{=} NP demonstra a importância desta classe para a ciência da computação
  • Mas por que um projetista de algoritmos deveria se preocupar?
  • Porque problemas NPNP-Completos são extremamente comuns
  • E existe pouca esperança de obter um algoritmo polinomial para eles

Problema NPNP-difícil

  • NPNP-difícil é o conjunto de problemas QQ tais que todo outro problema de NPNP é redutível a QQ

  • O problema QQ é pelo menos tão difícil quanto qualquer outro problema em NPNP

  • O problema QQ não precisa estar em NPNP, pois não precisa ser um problema de decisão.

  • Uma outra definição para NPNP-Completo são os problemas NP que são NPNP-difíceis.

Problema NPNP-difícil

  • Se PNPP \neq NP, então não existe solução polinomial para os problemas NPNP-Hard

Problemas NPNP-completos

  • Assim, se voce se deparar com um problema difícil
  • É importante saber verificar se ele é NP-Completo ou NPNP-Difícil
  • Para tratá-lo de modo adequado
  • Hoje não apresentamos opções para lidar com problemas NPNP-Completos
  • Mas mostramos como identificá-los