NP - Completo

Computabilidade

NP - COMPLETO

Aluno: Luiz Fernando Trindade Santos
Orientador: Clovis

Sumário
1- NP-COMPLETO .......................................................................................................................... 3
1.1- REDUTIBILIDADE EM TEMPO POLINOMIAL ....................................................................... 3
1.2 - DEFINIÇÃO ......................................................................................................................... 4
2- O TEOREMA DE COOK-LEVIN .................................................................................................... 5
3- PROBLEMAS NP-COMPLETOS ................................................................................................. 11
3.1- O PROBLEMA DA COBERTURA DE VÉRTICES.................................................................... 11

2|Página

1- NP-COMPLETO
Um importante avanço na questão P versus NP veio no início dos anos setenta com o trabalho de Stephen Cook e Leonid Levin. Eles descobriram certos problemas em
NP cuja complexidade individual está relacionada aquela da classe inteira. Se um algoritmo de tempo polinomial existe para algum desses problemas, todos os problemas em NP seriam solúveis em tempo polinomial. Esses problemas são chamados NPcompletos.
O primeiro problema NP-completo que apresentamos é chamado o problema da satisfatibilidade, que consiste testar se uma fórmula booleana é satisfatível, ou seja, se alguma atribuição de zeros e uns ás variáveis faz com que o valor da fórmula seja 1.
Assim:

Agora enunciamos o teorema de Cook–Levin que liga a complexidade do problema as complexidades de todos os problemas em NP.
•

Teorema Cook-Levin: SAT pertence a NP se somente se P = NP.

A seguir, desenvolvemos o método que é central para a prova do teorema de
Cook–Levin.

1.1- REDUTIBILIDADE EM TEMPO POLINOMIAL
A redubilidade leva em conta a eficiência da computação. Quando o problema A
é