Informática Teórica
Engenharia da Computação
COMPLEXIDADE DE TEMPO

Às vezes não é possível achar reduções
polinomiais para a busca de força bruta
– Às vezes nem se sabe se elas existem 
– Não se sabe porque certas reduções são
possíveis
 Que princípios?


Porém, as complexidades de muitos problemas
estão interligadas
Um algoritmo de tempo polinomial para um
desses problemas pode ser usado para resolver
uma classe inteira de problemas.
COMPLEXIDADE DE TEMPO

Um caminho hamiltoniano num grafo direcionado G
é um caminho direcionado que passa por cada nó
exatamente uma vez.
 Problema: testar se um grafo direcionado contem um
caminho hamiltoniano conectando 2 nós dados.
 HAMPATH = {<G,s,t>| G é um grafo direcionado com
um caminho hamiltoniano de s para t}
COMPLEXIDADE DE TEMPO

Podemos obter um algoritmo de tempo exponencial
para o problema HAMPATH modificando o algoritmo
de força-bruta para CAM dado
CLASSE P – PROBLEMAS

CAM = {<G,s,t> | G é um grafo direcionado que
tem um caminho de s para t }
CLASSE P – PROBLEMAS
TEOREMA
 CAM ∈ P

Estratégia força bruta
– Examina todos os caminhos potenciais em G
– Determinar se algum é um caminho direcionado de
s para t
– Caminho potencial: sequência de nós em G tendo
um comprimento de no máximo |V|
– Há aproximadamente |V||V| caminhos potenciais
– Tempo exponencial
CLASSE P – PROBLEMAS

IDÉIA DA PROVA: usar um método de busca no
grafo para evitar a força bruta.
– Busca em largura: marcamos sucessivamente
todos os nós que são atingíveis a partir de s por
caminhos de comprimento 1, depois 2, em
seguida 3 etc.
– Mostrar que a estratégia é polinomial

PROVA: o algoritmo seguinte M decide CAM em
tempo polinomial
CLASSE P – PROBLEMAS

M = “Sobre a entrada <G, s, t> onde G é um
grafo direcionado com nós s e t:
– 1. Marque o nó s.
– 2. Repita o passo seguinte até que nenhum nó
adicional seja marcado
 3. Para cada aresta (a,b) de G: se a for um nó
marcado e b não estiver marcado, marque b.
– 4. Se t estiver marcado, aceite. Senão, rejeite.”
CLASSE P – PROBLEMAS

Número de passos de M
– Os passos 1 e 4 executam apenas uma vez
– O passo 3 executa no máximo |V| vezes: no pior
caso, apenas um nó é marcado a cada vez, exceto
a última

Complexidade dos passos de M
– Os passos 1 e 4 são facilmente implementados em
tempo polinomial
– O passo 3 varre cada aresta e executa um teste
para ver se um nó está marcado
CLASSE P – PROBLEMAS

Conclusão da prova
– M executa uma quantidade de passos polinomial
na entrada
– Todos os passos de M rodam em tempo polinomial
na entrada
– Logo, M é polinomial
– CAM ∈ P

Exercício do livro: 7.8
CLASSE NP – HAMPATH





Precisamos apenas adicionar um teste para
verificar que o caminho atual é hamiltoniano.
Ninguém sabe se HAMPATH é solúvel em tempo
polinomial.
Mas ele tem verificabilidade polinomial,
importante para entender sua complexidade.
Não conhecemos uma forma polinomial de
determinar se um grafo contem um caminho
hamiltoniano...
Mas se tal caminho fosse descoberto (talvez
usando o algoritmo exponencial), poderíamos
facilmente convencer uma outra pessoa de sua
existência, simplesmente apresentando-o.
CLASSE NP – HAMPATH

Em outras palavras, verificar a existência de um
caminho hamiltoniano pode ser muito mais fácil
que determinar sua existência.
CLASSE NP – PROBLEMAS





Outro problema polinomialmente verificável é a
compostura.
Um no. natural é composto se é o produto de 2
inteiros maiores que 1 (i.e., não é primo).
COMPOSITES = {x|x = pq, para inteiros p,q > 1}
Ë fácil verificar que um no. é composto, só é
necessário um divisor desse no.
Recentemente, um algoritmo de tempo polinomial
para testar se um no. é primo ou composto foi
descoberto, mas ele é mais complicado que o
método acima para verificar compostura.
CLASSE NP – PROBLEMAS

Alguns problemas podem não ser
polinomialmente verificáveis.
 Ex: 𝐻𝐴𝑀𝑃𝐴𝑇𝐻, o complemento de HAMPATH.
 Mesmo se pudéssemos determinar se um grafo
realmente não tivesse um caminho hamiltoniano,
não conhecemos uma maneira de permitir a uma
outra pessoa verificar sua inexistência sem usar
o mesmo algoritmo de tempo exponencial para
fazer a determinação primeiramente.
VERIFICADOR
DEFINIÇÃO
 Um verificador para uma linguagem A é um
algoritmo V, onde:
 A = {w|V aceita <w,c> para alguma cadeia c}
 Medimos o tempo de um verificador somente em
termos do comprimento de w.
 Portanto um verificador de tempo polinomial
roda em tempo polinomial no comprimento de w.
 Uma linguagem A é polinomialmente
verificável se ela tem um verificador de tempo
polinomial.
VERIFICADOR






Um verificador usa informação adicional (c) para verificar
que uma cadeia w é um membro de A.
c é chamada certificado ou prova da pertinência a A.
Para verificadores polinomiais, o certificado tem
comprimento polinomial (no comprimento de w) porque
isso é tudo o que o verificador pode acessar no seu
limitante de tempo.
Para HAMPATH , um certificado para uma cadeia
<G,s,t>∈ HAMPATH é o caminho hamiltoniano de s a t.
Para COMPOSITES, um certificado para o no.composto
x é um de seus divisores.
O verificador checa em tempo polinomial que a entrada
está na linguagem quando ela recebe o certificado.
VERIFICADOR
DEFINIÇÃO
 NP é a classe de linguagens que têm verificadores
de tempo polinomial.




A classe NP contem muitos problemas de
interesse prático.
HAMPATH e COMPOSITES são membros de NP.
COMPOSITES é também membro de P, um
subconjunto de NP, mas provar esse resultado é
muito mais difícil.
O termo NP vem de tempo polinomial nãodeterminístico vindo de MTs não-determinísticas
de tempo polinomial. .
CLASSE NP


A seguir , uma MT não-determinística (MTND)
que decide HAMPATH em tempo polinomial
não-determinístico.
O tempo de uma MTND é o tempo usado pelo
seu ramo de computação mais longo.
CLASSE NP
N1 = “Sobre a entrada <G,s,t>, onde G é um grafo
direcionado com nós s e t:
 1. Escreva uma lista de m nos.p1... pm, m sendo o
no.de nós em G. Cada no. na lista é selecionado
não-deterministicamente entre 1 e m.
 2. Verifique se há repetições na lista. Se alguma for
encontrada, rejeite.
 3. Verifique se s = p1 e t = pm. Se algum falhar,
rejeite.
 4. Para cada i entre 1 e m-1, verifique se (pi,pi+1) é
aresta de G. Se alguma não for, rejeite. Senão, todos
os testes foram positivos, portanto aceite.”

CLASSE NP

Analisemos, examinando cada um de seus
estágios.
 No estágio 1, a escolha não-determinística
claramente roda em tempo polinomial.
 No 2 e 3, cada parte é uma simples verificação,
portanto juntos eles rodam em tempo polinomial.
 Finalmente, o estágio 4 também claramente roda
em tempo polinomial.
 Por conseguinte, esse algoritmo roda em tempo
polinomial não-determinístico.
NP
TEOREMA
 Uma linguagem está em NP sse ela é decidida por
uma MTND de tempo polinomial.
 IDEIA DA PROVA: 2 mãos:
 Mostramos como converter um verificador de
tempo polinomial para uma MTND de tempo
polinomial equivalente ...
 ...e vice versa.
 A MTND simula o verificador adivinhando o
certificado.
 O verificador simula a MTND usando o ramo de
computação de aceitação como o certificado.
NP
TEOREMA
 Uma linguagem está em NP sse ela é decidida por
uma MTND de tempo polinomial.
 PROVA: 1ª mão: Suponha que A ∈ NP e mostre
que A é decidida por uma MTND de tempo
polinomial N.
 Seja V o verificador de tempo polinomial para A
que existe pela definição de NP.
 Assuma que V seja uma MTND que roda em
tempo nk e construa N da seguinte maneira.
NP
TEOREMA
 Uma linguagem está em NP sse ela é decidida por
uma MTND de tempo polinomial.
 PROVA: 1ª mão:
 N = “Sobre a entrada w de comprimento n:
 1. Não-deterministicamente selecione uma cadeia
c de comprimento no máximo nk.
 2. Rode V sobre a entrada <w,c>.
 3. Se V aceita, aceite; caso contrário, rejeite.”
NP
TEOREMA
 Uma linguagem está em NP sse ela é decidida por
uma MTND de tempo polinomial.
 PROVA: 2ª mão: Assuma que A seja decidida por
uma MTND de tempo polinomial N e construa um
verificador de tempo polinomial V:
 N = “Sobre a entrada <w,c>.
 1. Simule N sobre a entrada w, tratando cada
símbolo de c como uma descrição da escolha nãodeterminística a fazer a cada passo (como na
prova do Teorema 3.16).
 2. Se esse ramo da computação de N aceita,
aceite; caso contrário,rejeite.”
NP
DEFINIÇÃO
 NTIME(t(n)) = {L|L é uma linguagem decidida por
uma MTND de tempo O(t(n))}.

Definimos a classe de complexidade de tempo
não-determinístico NTIME(t(n)) como análoga à
classe de complexidade de tempo determinístico
TIME(t(n)).
CLASSE NP
DEFINIÇÃO
NP = 𝑘 NTIME(𝑛𝑘 )


A classe NP é insensível à escolha do modelo
computacional não-determinístico razoável
porque todos esses modelos são
polinomialmente equivalentes.
Ao descrever e analisar algoritmos de tempo
polinomial não-determinísticos, seguimos as
convençoes precedentes para algoritmos
determinísticos de tempo polinomial.
CLASSE NP
DEFINIÇÃO
NP = 𝑘 NTIME(𝑛𝑘 )


Cada estágio de um algoritmo não-determinístico de
tempo polinomial deve ter uma implementação
óbvia em tempo polinomial não-determinístico em
um modelo computacional não-determinístico
razoável.
Analisamos o algoritmo para mostrar que todo ramo
usa no máximo uma quantidade polinomial de
estágios.
CLASSE NP – PROBLEMAS

Um clique em um grafo não-direcionado é um
subgrafo, no qual todo par de nós está conectado
por uma aresta.
 Um k-clique é um clique que contem k nós.
 CLIQUE = {<G,k>|G é um grafo não-direcionado
com um k-clique}:
CLASSE NP – PROBLEMAS
TEOREMA
 CLIQUE está em NP.






IDEIA DA PROVA: O clique é o certificado.
PROVA Aqui está um verificador V para CLIQUE:
V = “Sobre a entrada <<G,k>,c>:
1. Teste se c é um conjunto de k nós em G
2. Teste se G contem todas as arestas
conectando nós em c.
3. Se ambos os testes retornam positivo, aceite;
caso contrário, rejeite.”
CLASSE NP – PROBLEMAS
TEOREMA
 CLIQUE está em NP.
 PROVA ALTERNATIVA, em termos de MTNDs:
 É só fornecer uma que decida CLIQUE.
 Observe a similaridade entre as duas provas.




N = “Sobre a entrada <G,k>, onde G é um grafo:
1. Não-deterministicamente selecione um
subconjunto c de k nós de G.
2. Teste se G contem todas as arestas
conectando nós em c.
3. Se sim, aceite; caso contrário, rejeite.”
CLASSE NP – PROBLEMAS


Seja uma coleção de nos.x1...xk e um no.alvo t.
Desejamos determinar se a coleção contem uma
subcoleção que soma t.

SUBSET-SUM = {<S,t>|S = {x1...xk} e para algum
{y1...yl} ⊆ {x1...xk} temos Σyi = t}

<{4,11,16,21,27},25>∈SUBSET-SUM pois 4+21=25.

Note que {x1...xk} e {y1...yl} são considerados como
multiconjuntos então permitem repetição de
elementos.
CLASSE NP – PROBLEMAS
TEOREMA
 SUBSET-SUM está em NP.






IDEIA DA PROVA: O subconjunto é o certificado.
PROVA Eis um verificador V para SUBSET-SUM:
V = “Sobre a entrada <<S,t>,c>:
1. Teste se c é uma coleção de nos que somam t.
2. Teste se S contem todos os nos. em c.
3. Se ambos os testes retornam positivo, aceite;
caso contrário, rejeite.”
CLASSE NP – PROBLEMAS
TEOREMA
 SUBSET-SUM está em NP.
 PROVA ALTERNATIVA, em termos de MTNDs:




N = “Sobre a entrada <S,t>:
1. Não-deterministicamente selecione um
subconjunto c dos nos. em S.
2. Teste se c é uma coleção de nos.que somam t.
3. Se sim, aceite; caso contrário, rejeite.”
CLASSE NP – PROBLEMAS

Os complementos 𝐶𝐿𝐼𝑄𝑈𝐸e SUBSET−SUM não
são obviamente membros de NP.

Verificar que algo não está presente parece ser
mais difícil que verificar que está presente.

Fazemos uma classe de complexidade separada,
chamada coNP, que contem as linguagens que
são complementos de linguagens em NP.

Não sabemos se coNP é diferente de NP.
P=NP?





NP é a classe de linguagens solúveis em tempo
polinomial numa MTND, ou,
NP é a classe de linguagens onde a pertinência
na linguagem pode ser verificada em tempo
polinomial.
P é a classe de linguagens onde a pertinência
pode ser testada em tempo polinomial.
HAMPATH, CLIQUE ∈ NP
HAMPATH, CLIQUE ∈ P ?
P=NP?






O poder de verificabilidade polinomial parece ser muito
maior que aquele da decidibilidade polinomial.
Mas, P e NP podem ser iguais.
Somos incapazes de provar a existência de uma única
linguagem em NP que não esteja em P.
A maioria dos pesquisadores acreditam que as duas
classes não são iguais porque houve esforços enormes
para encontrar algoritmos de tempo polinomial para certos
problemas em NP, sem sucesso.
Pesquisadores também têm tentado provar que as classes
são diferentes, mas isso acarretaria mostrar que nenhum
algoritmo rápido existe para substituir a força-bruta.
Fazer isso está atualmente além do alcance científico.
P=NP?

O melhor método conhecido para resolver linguagens
em NP deterministicamente usa tempo exponencial.

Podemos provar que:
𝑛𝑘

NP ⊆ EXPTIME =

Mas não sabemos se NP está numa classe de
complexidade de tempo determinístico menor.
𝑘 TIME(2
)
NP-COMPLETUDE






Cook – 1971 – NP
Levin – 1973 – problemas de busca
Karp – 21 problemas NP
Eles descobriram certos problemas NP cuja
complexidade individual está relacionada à
classe NP inteira.
Se um algoritmo de tempo polinomial existe para
quaisquer desses problemas, todos os problemas
em NP seriam solúveis em tempo polinomial.
Esses problemas são chamados NP-completos.
NP-COMPLETUDE

O fenômeno da NP-completude é importante por
razões tanto teóricas quanto práticas.
 No lado teórico, um pesquisador tentando mostrar
que P é diferente de NP pode focar sobre um
problema NP-completo.
 Se algum problema em NP requer mais que tempo
polinomial, um NP-completo também requer.
 Um pesquisador tentando provar que P=NP só
precisa encontrar um algoritmo polinomial para um
problema NP-completo para atingir seu objetivo.
 No lado prático, a NP-completude pode evitar a
perda de tempo buscando por um algoritmo
polinomial inexistente para um problema específico
NP-COMPLETUDE

Muito embora possamos não ter a matemática
necessária para provar que o problema é insolúvel
em tempo polinomial, acreditamos que P≠NP.

Portanto provar que um problema é NP-completo é
forte evidência de sua não-polinomialidade.

SAT = {<F>| F é uma fórmula booleana satisfatível}

TEOREMA DE COOK-LEVIN: SAT ∈ P sse P=NP.
REDUTIBILIDADE EM TEMPO POLINOMIAL


Agora definimos uma versão de redutibilidade em
relação à eficiência da computação.
Quando o problema A é eficientemente redutível a B,
a solução eficiente para B pode ser usada para A.
REDUTIBILIDADE EM TEMPO POLINOMIAL
DEFINIÇÕES
 Uma função f:Σ ∗ Σ ∗ é computável em tempo
polinomial se alguma MT polinomial M existe que
pára com exatamente f(w) na sua fita, quando
iniciada sobre qualquer entrada w.

A linguagem A é redutível (por mapeamento) em
tempo polinomial (muitos-para-um), à linguagem B
(A ≤𝑷 B), se uma função computável polinomial
f:Σ ∗ Σ ∗ existe, onde para toda w, w ∈ A ⇔ f(w) ∈ B:

A função f é chamada redução de tempo polinomial
de A para B.
REDUTIBILIDADE EM TEMPO POLINOMIAL
TEOREMA
 Se A ≤𝑷 B e B ∈ P, então A ∈ P.





PROVA : Seja M o algoritmo polinomial que decide B
e f a redução polinomial de A para B.
Eis um algoritmo polinomial N que decide A:
N = “Sobre a entrada w:
1. Compute f(w).
2. Rode M sobre a entrada f(w) e dê como saída a
saída de M.”
REDUTIBILIDADE EM TEMPO POLINOMIAL
TEOREMA
 Se A ≤𝑷 B e B ∈ P, então A ∈ P.

PROVA:
 w ∈ A sempre que f(w) ∈ B porque f é uma redução
de A para B.
 Portanto, M aceita f(w) sempre que w ∈ A.


Ademais, N é polinomial pois cada um de seus 2
estágios roda em tempo polinomial.
O estágio 2 é polinomial porque a composição de
polinômios é um polinômio.
3-SAT



1-SAT:linear (um literal por
subfórmula)
2-SAT: linear (com fases)


– (x11 OR x12) AND
(x21 OR x22) AND
(x31 OR x32) AND…
3-SAT: NP-completo
– (x11 OR x12 OR x13) AND
(x21 OR x22 OR x23) AND
(x31 OR x32 OR x33) AND ...
– O problema são os conflitos, que
diminuem a satisfabilidade!
Não existe um algoritmo
polinomial para todas as
instâncias do problema
SAT, a não ser que P = NP
Vira deterministicamente
polinomial quando as
sentenças viram
– 2-SAT (no máximo 2
símbolos proposicionais
por fórmula)
– Cláusula de Horn – 1SAT (No máximo 1
símbolo proposicional
positivo em todas as subfórmulas)
REDUTIBILIDADE EM TEMPO POLINOMIAL
3SAT = {<F>| F é uma 3fnc-fórmula satisfatível}
TEOREMA
 3SAT é redutível em tempo polinomial a CLIQUE.



IDEIA DA PROVA: A redução de tempo polinomial f de
3SAT para CLIQUE converte fórmulas para grafos.
Nos grafos construídos, cliques de um dado tamanho
correspondem a atribuições que satisfazem a fórmula.
Estruturas dentro do grafo são projetadas para imitar o
comportamento das variáveis e cláusulas.
REDUTIBILIDADE EM TEMPO POLINOMIAL
TEOREMA
 3SAT é redutível em tempo polinomial a CLIQUE.
 PROVA: Seja F com k cláusulas tal como
 = (a1 v b1 v c1) ^ (a2 v b2 v c2) ^ ... ^ (ak v bk v ck)
 A redução f gera a cadeia <G,k> onde G é um grafo nãodirecionado definido da seguinte forma.
 Os nós em G são organizados em k grupos de 3 nós.
 Cada tripla ti corresponde a uma das k cláusulas.
 As arestas de G conectam todos exceto dois tipos de
pares de nós em G:
– Nenhuma aresta existe entre nós na mesma tripla.
– Não há aresta entre 2 nós contraditórios.
REDUTIBILIDADE EM TEMPO POLINOMIAL
TEOREMA
 3SAT é redutível em tempo polinomial a CLIQUE.

F= (x1 v x1 v x2) ^ (~x1 v ~x2 v ~x2) ^ (~x1 v x2 v x2):
REDUTIBILIDADE EM TEMPO POLINOMIAL
TEOREMA
 3SAT é redutível em tempo polinomial a CLIQUE.
 PROVA: Numa atribuição que satisfaz F, pelo menos um
literal é T em toda cláusula.
 Em cada tripla de G, selecionamos um nó de um literal
verdadeiro na atribuição que satisfaz F.
 Os nós selecionados formam um k-clique.
 O número de nós selecionado é k, porque escolhemos
um para cada uma das k triplas.
 Cada par de nós selecionados é ligado por uma aresta
porque nenhum par se encaixa numa das exceções.
DEFINIÇÃO DE NP-COMPLETUDE
DEFINIÇÃO
 Uma linguagem B é NP-completa se satisfaz :
 1. B está em NP, e
 2. toda A em NP é redutível em tempo polinomial a B.
TEOREMA
 Se B for NP-completa e B ∈ P, então P = NP.

PROVA Esse teorema segue diretamente da definição
de redutibilidade de tempo polinomial.
DEFINIÇÃO DE NP-COMPLETUDE
TEOREMA
 Se B for NP-completa e B ≤𝑷 C para C em NP, então C é
NP-completa.
 PROVA:C está em NP, portanto devemos mostrar que
toda A em NP é redutível em tempo polinomial a C.
 Em razão de B ser NP-completa, toda linguagem em NP
é redutível em tempo polinomial a B.
 B por sua vez é redutível em tempo polinomial a C.
 Reduções em tempo polinomial se compõem;i.e., se A
for redutível em tempo polinomial a B e B for redutível
em tempo polinomial a C, então A é redutível em tempo
polinomial a C. Logo, toda linguagem em NP é redutível
em tempo polinomial a C.
COOK-LEVIN

Vide livro
O PROBLEMA DA COBERTURA DE VÉRTICES



Se G é um grafo não-direcionado, uma cobertura de
vértices de G é um subconjunto dos nós onde toda
aresta de G toca um daqueles nós.
O problema da cobertura de vértices pergunta se um
grafo contem uma cobertura de vértices de um
tamanho especificado.
COBERT-VERTICE = f{<G; k>| G é um grafo nãodirecionado que tem uma cobertura de vértices de knós}
O PROBLEMA DA COBERTURA DE VÉRTICES
TEOREMA
 COBERT-VERTICE é NP-completo.
 IDEIA DA PROVA: 2 provas:
 COBERT-VERTICE é NP: certificado
– uma cobertura de vértices de tamanho k

Todos os NP são polinomialmente redutíveis a ele.
– 3SAT ≤𝑷 COBERT-VERTICE.
 converte ruma 3fnc-fórmula F num grafo G e um no. k,
 F é satisfatível se G tem uma cobertura de vértices com k nós
O PROBLEMA DA COBERTURA DE VÉRTICES
TEOREMA
 COBERT-VERTICE é NP-completo.
 PROVA: 3SAT ≤𝑃 COBERT-VERTICE.
 A redução mapeia uma fórmula booleana para um grafo G
e um valor k. Para cada variável x em F, produzimos uma
aresta conectando 2 nós (x e ~x)
 Cada engrenagem de cláusulas é uma tripla de 3 nós
rotulados com os literais da cláusula, conectados um ao
outro e aos nós nas engrenagens de variáveis que têm os
rótulos idênticos.
 O total de nós que aparecem em G é 2m+3l, onde F tem
m variáveis e l cláusulas. Suponha k = m + 2l.
O PROBLEMA DA COBERTURA DE VÉRTICES
TEOREMA
 COBERT-VERTICE é NP-completo.
 PROVA: 3SAT ≤𝑃 COBERT-VERTICE.
O PROBLEMA DA COBERTURA DE VÉRTICES
TEOREMA
 COBERT-VERTICE é NP-completo.
 PROVA: 3SAT ≤𝑃 COBERT-VERTICE.
 F é satisfatível sse o grafo G tiver uma cobertura de K
nós!
O PROBLEMA DA SOMA DE SUBCONJUNTOS
TEOREMA
 SUBSET-SUM é NP-completo.
 IDEIA DA PROVA: 2 provas
 SUBSET-SUM é NP.
 3SAT ≤𝑃 SUBSET-SUM
– Dada uma 3fnc-fórmula F construímos uma instância de
SUBSET-SUM contendo uma subcoleção T cuja soma é o
alvo t sse F é satisfatível.
– A instância de SUBSET-SUM construída cont´em nos.
grandes em notação decimal.
– Variáveis são pares de nos.e cláusulas certas posições nas
representações decimais dos números.
Informática Teórica
Engenharia da Computação