NP-Completude

PROBLEMAS NP-COMPLETOS

UNIFESP
Trabalho Extra de Projeto e Análise de Algoritmos
Aluno: Julio Cesar Nogueira de Oliveira
R.A .: 75356

OS CONJUNTOS P e NP

A classe de problemas “P” refere-se àqueles que podem ser resolvidos em tempo polinomial, ou seja em um tempo O(nk), pra alguma constante “k”, e “n” é o tamanho da entrada para o problema.

Existem problemas que podem ser verificados em tempo polinomial. A estes atribuiu-se a denominação “NP”, que é um é o acrônimo em inglês para Tempo polinomial não determinístico (Non-Deterministic Polynomial time) .

Qualquer problema em P também esta em NP.

Assim, este trabalho tem por objetivo apresentar uma prova da NP-completude do problema 3SAT. Para tanto, a seguir é dada a definição do problema, assim como definições necessárias à prova, bem como a descrição do modelo de prova em si. Satisfabilidade

Uma fórmula satisfazível é uma fórmula verdadeira sob alguma interpretação. Por exemplo, (x ∧ y) é uma fórmula satisfazível sob a interpretação onde a (x e y) são atribuídos valores verdadeiros, ao passo que (x ∧ ¬x) não é uma fórmula satisfazível sob qualquer interpretação.

Uma fórmula CNF (Conjuntive Normal Form) é uma conjunção de i cláusulas C, cada uma sendo uma disjunção de termos. Por exemplo, (a)∧(b∨c)∧(¬a∨b∨¬c∨d ∨ ¬e) é uma fórmula CNF válida. Uma fórmula 3-CNF é uma conjunção de i cláusulas C, cada uma sendo uma disjunção de no máximo três termos. Por exemplo, (a) ∧ (b ∨ c) ∧ (¬a ∨ b ∨ ¬c) é uma fórmula 3-CNF válida.

Sendo assim, pode-se definir o problema 3SAT como sendo o conjunto de todas as fórmulas 3-CNF satisfazíveis, e o problema SAT como sendo o conjunto de todas as fórmulas CNF satisfazíveis.

Redutibilidade Uma redução polinomial é um procedimento que transforma em tempo poli- nomial uma instância α de um problema A em uma instância β de um problema B, de modo que α e β sejam equivalentes. Esta redução é expressa