A Classe NP
Teoria da Computação
Profa. Sandra de Amo
Definição de NP
NP = {A | A é decidida por uma M.T. M, não determinista a
uma fita, tal que NTimeM(n) = O(nk)}
O que é NTimeM(n) ?
• Considere um input w de tamanho n
• Considere a árvore de execução Arv de M em w
• A árvore Arv(w) é finita, pois M decide A.
• Considera p(w) = o comprimento do maior ramo de
Arv(w)
NTimeM(n) = max{p(w) | |w| = n }
Verificador versus Decididor
• Seja A um problema. Um verificador para
o problema A é uma M.T V determinista a
uma fita tal que
qa se c é uma “prova” de
w é input positivo de A
<w,c>
V
qr se c é um “indicio” de
w pode ser
input negativo de A
101101111 011111
Input w
Certificado c
Teorema
• Um problema A é NP se e somente se tem um
Verificador V tal que TimeV(n) = O(nk), isto é um
Verificador polinomial
• Veja que o fato de A estar em NP significa que
tem um Decididor exponencial
• Isto é:
decididor exponencial  verificador polinomial
Lembrando: Transformação MT
Não-det em MT determinista
FITA DE INPUT
0
0
1
1
FITA DE CÁLCULO
FITA DAS POSSIBILIDADES
1
1
2
Serão executados 3 passos de M’
Passo 1 : opção 1
Passo 2 : opção 1
Passo 3 : opção 2
Demonstração (ida)
Suponha que o problema A tenha um verificador V em tempo polinomial. Vamos
construir uma M.T. N não-determinista que o decide em tempo polinomial.
V pára sempre em qualquer input <w,c> em um número de passos p(n), onde p =
polinomio em n, n = tamanho do input w
Logo, os certificados possiveis de V tem no máximo tamanho p(n), sendo portanto em
um número finito.
A máquina N é definida como:
N = No input w faça,
1.
Escolhe um string c dentre os possiveis certificados de V
2.
Execute V em <w,c>
3.
Se V aceita, N pára em qa
4.
Se V rejeita, N pára em qr
Número de passos de N é polinomial, pois o tamanho de c é polinomial em n e o número
de passos de V é polinomial em n.
Demonstração (volta)
Suponha que o problema A seja decidível por uma máquina de Turing N, nãodeterminista a uma fita, em tempo polinomial. Vamos construir verificador
polinomial para A.
Seja a = número máximo de opções dos comandos de N
Seja w um input de N de tamanho n
p(n) = tamanho máximo dos ramos da árvore de execução de N ao ser executada em w.
Todos os ramos são finitos e terminam em qa ou qr.
Considere todos os strings c de comprimento no máximo p(n) sobre o alfabeto {1,...,a}.
Cada string c representa uma possivel execução de N em w.
V = No input <w,c> faça
1. Execute a sequência de operações de N (em w) indicadas pelo string c, como uma
escolha possivel para N
2. Se este ramo de N pára em qa, V pára em qa
3. Se este ramo de N pára em qr, V pára em qr.
V é um verificador para A, em tempo polinomial, já que o string c tem comprimento
polinomial em n e “dita” o número de operações a serem executadas
Classes de Complexidade
• P  NP
• NP  EXP
– Toda máquina não-det N de tempo polinomial p(n) é
equivalente a uma máquina det a 3 fitas M de tempo
exponencial 2O(p(n)).
– Esta máquina M com 3 fitas pode ser transformada
em uma outra máquina determinista com 1 fita com
complexidade 2O(p2(n)).
• Uma destas inclusões é estrita 
– pois P  EXP
• Problema em aberto desde os anos 70 : qual
delas ???