Problemas NP-Completos

Problemas NP-Completos

• Classe NP
• SAT
• Definição
• Motivação
• SAT é NP-Completo
• 3SAT é NP-Completo
 CLASSE NP
Classe de Modelo de
Recurso
• A classe NP é a classe dos Complexidade computação

problemas que consomem tempo DTIME(f(n)) MTD Tempo O(f(n))

polinomial em uma MTND P MTD 𝐷𝑇𝐼𝑀𝐸(𝑛 )

NTIME(f(n)) MTND Tempo O(f(n))

NP MTND 𝑁𝑇𝐼𝑀𝐸(𝑛 )

• Exemplo:
• SAT (se uma fórmula  do cálculo proposicional é Satisfatível)
• Não conhecemos algoritmos polinomiais para SAT
 SAT
O problema SAT consiste em determinar se uma
determinada fórmula  é satisfazível.

Exemplo:

 = (p1 p2)(p1  p2)

 SAT
SAT  NP.
 = (p1 p2)(p1  p2)
i) Um certificado será uma atribuição, uma linha da
tabela verdade, por exemplo: p1=1 e p2=0.
ii) Podemos parsear  e colocá-la na forma de árvore
em tempo linear:


 

p1 p2 𝒑𝟏 𝒑𝟐

iii) Substituir a atribuição nas folhas e avaliar a árvore.

 PROBLEMA NP-DIFÍCIL
Um linguagem 𝐿2 é NP-difícil se qualquer linguagem em NP pode
ser reduzido a 𝐿2 por uma redução polinomial.

A ideia para provar que 𝐿2 é NP-Difícil é que se 𝐿1 ∈ 𝑁𝑃, então,

dado 𝜔 podemos construir 𝑒𝑑𝑖𝑡𝑎(𝜔) em tempo polinomial, tal
que:

𝐶 𝜔 = 𝐶 (𝑒𝑑𝑖𝑡𝑎(𝜔))

Portanto se existe uma solução polinomial para 𝐿2 existe uma

solução polinomial para todo problema 𝐿1 em 𝑁𝑃.
 PROBLEMA NP-COMPLETO
Se um problema está em NP e é NP-difícil chamamos o problema
de NP-completo.

SAT é NP-completo. [Stephen Cook, 1971] [Ind. p/ Leonid Levin]

 MOTIVAÇÃO
• Como justificar ao seu chefe que você não consegue um algoritmo
eficiente para criar um projeto de um Odradek a partir de sua
especificação?
 MOTIVAÇÃO
• Infelizmente você não pode afirmar sem prova..
 MOTIVAÇÃO
• Talvez este motivo seja tão bom quanto o anterior..
 PROBLEMA NP-DIFÍCIL
Um linguagem 𝐿2 é NP-difícil se qualquer linguagem em NP pode
ser reduzido a 𝐿2 por uma redução polinomial.

A ideia para provar que 𝐿2 é NP-Difícil é que se 𝐿1 ∈ 𝑁𝑃, então,

dado 𝜔 podemos construir 𝑒𝑑𝑖𝑡𝑎(𝜔) em tempo polinomial, tal
que:

𝐶 𝜔 = 𝐶 (𝑒𝑑𝑖𝑡𝑎(𝜔))

Portanto se existe uma solução polinomial para 𝐿2 existe uma

solução polinomial para todo problema 𝐿1 em 𝑁𝑃.
 PROBLEMA NP-DIFÍCIL

Karp Reduction
𝐶 𝜔 = 𝐶 (𝑒𝑑𝑖𝑡𝑎(𝜔)) 𝐿1 ≤ 𝐿2
𝐿1 ≤ 𝐿2

• 𝐶 𝜔 ={
• .... Cook Reduction
• 𝑋 ← 𝐶 (𝑒𝑑𝑖𝑡𝑎(𝜔)) Polynomial Turing Reduction
• .... 𝐿1 ≤ 𝐿2
• 𝑂𝑈𝑇𝑃𝑈𝑇 𝑌
• }
 PROBLEMA NP-DIFÍCIL

Karp Reduction
𝐶 𝜔 = 𝐶 (𝑒𝑑𝑖𝑡𝑎(𝜔)) 𝐿1 ≤ 𝐿2
𝐿1 ≤ 𝐿2

• 𝐶 𝜔 ={
• .... Cook Reduction
• 𝑋 ← 𝐶 (𝑒𝑑𝑖𝑡𝑎(𝜔)) Polynomial Turing Reduction
• .... 𝐿1 ≤ 𝐿2
• 𝑂𝑈𝑇𝑃𝑈𝑇 𝑌
• }
 PROBLEMA NP-COMPLETO
Se um problema está em NP e é NP-difícil chamamos o problema
de NP-completo.

SAT é NP-completo. [Stephen Cook, 1971] [Ind. p/ Leonid Levin]

 TEOREMA DE COOK-LEVIN
SAT é NP-completo. [Stephen Cook, 1971] [Ind. p/ Leonid Levin]

Já vimos que SATNP. Para provar que SAT é NP-Completo falta

provar que SAT é NP-difícil. A ideia é que se uma linguagem 𝐿 é
reconhecida em tempo 𝑚 (polinomial em |𝜔|) por uma MTND 𝑀,
então, dado 𝜔 podemos construir uma fórmula 𝜑 𝑀, 𝜔 =
𝑒𝑑𝑖𝑡𝑎(𝜔) em tempo 𝑂(𝑚 ), portanto 𝜑 𝑀, 𝜔 = 𝑂(𝑚 ), tal
que:
𝐶 𝜔 = 𝑆𝐴𝑇(𝑒𝑑𝑖𝑡𝑎(𝜔))

Portanto se existe uma solução polinomial para 𝑆𝐴𝑇 existe uma

solução polinomial para todo problema em 𝑁𝑃.
𝐿 = 𝑇(𝑀) ≤ 𝑆𝐴𝑇

𝑁𝑃 ⊆ 𝑃 =𝑃
 TEOREMA DE COOK-LEVIN
• Se 𝐿 ∈ 𝑁𝑃 então existe uma máquina de Turing não determinística 𝑀 que
reconhece 𝐿 em tempo polinomial.
• Se 𝑤 ∈ 𝐿 tem tamanho 𝑛 então a máquina de Turing começa com 𝑛
caracteres e faz 𝑚 movimentos onde 𝑚 ≤ 𝑃(𝑛) para algum polinômio 𝑃(𝑛)
de grau 𝑘.
0 0 1 1

q0

X 0 1 1
𝑚 ≤ 𝑃 𝑛 passos
q1

X Y X X Y 1 0 1 1 1 Z

q2

𝑚 ≤ 𝑚 símbolos não brancos

 TEOREMA DE COOK-LEVIN
Variáveis Significado Qtd O()
Ti,j,k j   está na posição i no passo k 𝑚. Σ . 𝑚 O(p(n)2)
Hi,k Cabeça de leitura na posição i no passo k 𝑚. 𝑚 O(p(n)2)
Qq,k M está no estado q no passo k 𝑄 .𝑚 O(p(n))

H0,0 Qq0,0 T0,0,0 T1,0,0 T2,1,0 T3,1,0 T4,B,0 T5,B,0

V V V V V V V V

H1,1 Qq1,1 T0,X,1 T1,0,1 T2,1,1 T3,1,1 T4,B,1 T5,B,1

V V V V V V V V
 CONDIÇÃO INICIAL
Variáveis Significado Qtd O()
Ti,j,k j   está na posição i no passo k 𝑚. Σ . 𝑚 O(p(n)2)
Hi,k Cabeça de leitura na posição i no passo k 𝑚. 𝑚 O(p(n)2)
Qq,k M está no estado q no passo k 𝑄 .𝑚 O(p(n))

H0,0 Qq0,0 T0,0,0 T1,0,0 T2,1,0 T3,1,0 T4,B,0 T5,B,0

V V V V V V V V

• Abaixo as necessidades para amarrar a condição inicial.

• Não precisamos colocar as fórmulas negadas se especificarmos que existe no máximo 1
caractere por posição/passo, no máximo um estado por passo, etc.

Fórmula Condição Significado Qtd

Ti,wi ,0 Se i |w| Estado Inicial da Fita O(n)
Ti,B ,0 Se i >|w| Estado Inicial da Fita O(p(n))
Qs,0 Estado Inicial de M. 1
H0,0 Posição Inicial da cabeça 1
 RESTRIÇÕES DE FUNCIONAMENTO
Variáveis Significado Qtd O()
Ti,j,k j   está na posição i no passo k 𝑚. Σ . 𝑚 O(p(n)2)
Hi,k Cabeça de leitura na posição i no passo k 𝑚. 𝑚 O(p(n)2)
Qq,k M está no estado q no passo k 𝑄 .𝑚 O(p(n))

• Abaixo as restrições para funcionamento correto da MT.

• Para ser uma MT a fórmula tem que ser SAT.

Fórmula Condição Significado Qtd

¬Ti,j,k ∨ ¬Ti,j′,k j ≠ j′ No máximo um j   por posição O(p(n)2)
⋁j ∈ Σ Ti,j,k No mínimo um j   por posição O(p(n)2)
Ti,j,k ∧ Ti,j′,k+1 → Hi,k j ≠ j′ Só a cabeça modifica a fita. O(p(n)2)
¬Qq,k ∨ ¬Qq′,k q ≠ q′ Só um estado por vez O(p(n))
¬Hi,k ∨ ¬Hi′,k i ≠ i′ Só um posição da cabeça por vez O(p(n)3)
 RESTRIÇÕES DE FUNCIONAMENTO
Variáveis Significado Qtd O()
Ti,j,k j   está na posição i no passo k 𝑚. Σ . 𝑚 O(p(n)2)
Hi,k Cabeça de leitura na posição i no passo k 𝑚. 𝑚 O(p(n)2)
Qq,k M está no estado q no passo k 𝑄 .𝑚 O(p(n))

• Abaixo as restrições para implementação da função delta

(representada por quíntuplas), a direção d é representada por +1()
ou –1(). Variáveis com índice negativo podem ser omitidas do .
• Restrição para atingir o estado final da máquina, podemos usar a
definição alternativa de que a máquina reconhece quando ‘toca’ um
estado final, isso não altera a complexidade polinomial.

Fórmula Significado Qtd

(Hi+d,k+1 ∧ Qq′,k+1 ∧ Ti,σ′,k+1) → ⋁(q, σ, q′, σ′, d) ∈ δ (Hi,k ∧ Qq,k ∧ Ti,σ,k) para k<p(n).
O(p(n)2)
Implementa .
⋁ 0≤k≤p(n) ⋁f ∈ F Qf,k Termina em um estado final em até p(n) passos. 1
 M reconhece L em tempo p(n), ou seja LNP e w*.
Seja  w a conjunção das fórmulas das tabelas. SAT(w)  wL
Variáveis Significado Qtd
Ti,j,k j   está na posição i no passo k O(p(n)2)
Hi,k Cabeça de leitura está na posição i no passo k O(p(n)2)
Qq,k M está no estado q no passo k O(p(n))

Fórmula Condição Significado Qtd

Ti,wi ,0 Se i |w| Estado Inicial da Fita O(n)
Ti,B ,0 Se i >|w| Estado Inicial da Fita O(p(n))
Qs,0 Estado Inicial de M. 1
H0,0 Posição Inicial da cabeça 1
¬Ti,j,k ∨ ¬Ti,j′,k j ≠ j′ No máximo um símbolo de  por posição O(p(n)2)
⋁j ∈ Σ Ti,j,k No mínimo um símbolo de  por posição O(p(n)2)
Ti,j,k ∧ Ti,j′,k+1 → Hi,k j ≠ j′ Só a cabeça modifica a fita. O(p(n)2)
¬Qq,k ∨ ¬Qq′,k q ≠ q′ Só um estado por vez O(p(n))
¬Hi,k ∨ ¬Hi′,k i ≠ i′ Só um posição da cabeça por vez O(p(n)3)
(Hi+d,k+1 ∧ Qq′,k+1 ∧ Ti,σ′,k+1) → ⋁(q, σ, q′, σ′, d) ∈ δ (Hi,k ∧ Qq,k ∧ Ti,σ,k) para
O(p(n)2)
k<p(n). Implementa .
⋁ 0≤k≤p(n) ⋁f ∈ F Qf,k Termina em um estado final em até p(n) passos. 1
 SAT
Dada uma MTND 𝑴 que reconhece 𝐿 em tempo 𝑝(𝑛) e 𝜔 ∈ Σ ∗ , podemos ter um
programa que constrói 𝜑(𝑀, 𝜔) em tempo O 𝑝(𝑛) , vamos chamá-lo de
𝐶𝑂𝑂𝐾 𝑀, 𝜔, 𝑝(𝑛) , ou seja 𝜑 𝑀, 𝜔 = 𝐶𝑂𝑂𝐾 𝑀, 𝜔, 𝑝(𝑛) = 𝑒𝑑𝑖𝑡𝑎(𝜔).

Importante observar que:

SAT 𝜑 𝑀, 𝜔 ⟺ 𝜔 ∈ 𝑇(𝑀)

Isso 𝑇(𝑀) ≤ 𝑆𝐴𝑇 porque:

𝐶 𝜔 = SAT 𝐶𝑂𝑂𝐾 𝑀, 𝜔, 𝑝(𝑛) = 𝑆𝐴𝑇(𝑒𝑑𝑖𝑡𝑎(𝜔))
Logo, se SAT tem algoritmo polinomial e 𝐿 = 𝑇(𝑀) teremos L ∈ 𝑃,
consequentemente P = NP.
 PROBLEMA NP-COMPLETO
Os problemas NP-completos são os mais difíceis da classe NP.

P=NP NP-completo
NP-Completo

NPI
P

P
 PROBLEMA NP-COMPLETO
Os problemas NP-completos são os mais difíceis da classe NP.

P=NP NP-completo
NP-Completo

NPI

P
P
 PROBLEMA NP-COMPLETO
Os problemas NP-completos são os mais difíceis da classe NP.

P=NP NP-completo

NPI

P
 3SAT
O problema 3SAT consiste em determinar se uma
determinada fórmula  escrita em 3-CNF é satisfazível.
Estar escrita em 3-CNF significa estar na forma normal
conjuntiva onde cada MAXTERMO tem apenas 3
ocorrências de variável.
Exemplo:
= (p1 p2  p3) (p1  p2 p3)
• Lembramos que 2SAT  P.
• Qual será a complexidade de 3SAT?
 3SAT
• Vamos transformar o MAXTERMO:
=p1∨ ... ∨pn
• Em n–2 MAXTERMOS:
edita()=(p1 ∨ p2∨x2) ∧ (¬x2∨p3∨x3) ∧ (¬x3∨p4∨x4)∧...∧(¬xn − 2∨ pn-1∨pn)

• Exemplo:
=p1∨¬p2∨p3∨¬p4
edita()=(p1∨¬p2∨x2) ∧ (¬x2∨p3∨¬p4)

•  é satisfatível  edita() é satisfatível

• SAT() = 3SAT(edita())
• Se o número de átomos de  é n, o número de átomos de edita() é
3n – 3, portanto a redução é polinomial.
• 3SAT é NP-completo.
 Exercício
• A MT abaixo reconhece 𝐿 = 𝑤 # 𝑤 = # 𝑤 }
1. Para a entrada 0011 determine: Ti,j,k, Hi,k, Qq,k , para k=0 (basta listar os 1)
2. Quais são os valores de 𝑘 para essa entrada?
3. Quais são os valores de 𝑘 para para uma entrada 𝑤, 𝑤 = 𝑛 ?

/ 
q6 qf

/ 
X/X X/X
1/1
1/1 
X/X 

q0
0/𝑋 q1

/  / 

X/X 1/𝑋 0/0

q3 q2 X/X 
0/0 
Classe co-NP
 Classe co-NP

• Definição
• Composto
• Primo
• Caracterização
• TAUT é co-NP
• TAUT é co-NP completo