Classes P, NP e Reduções

Saber que um problema é NP-completo é uma das informações mais úteis que se pode ter sobre ele — não porque resolve, mas porque redireciona o esforço. Deixa-se de procurar algoritmo exato eficiente e passa-se a buscar aproximação, heurística ou restrição do caso de uso.

As classes

P: problemas de decisão resolvíveis em tempo polinomial por máquina determinística.

NP: problemas cuja solução pode ser verificada em tempo polinomial. Equivalentemente, resolvíveis em tempo polinomial por máquina não determinística.

A leitura por verificação é a mais útil. Um problema está em NP quando, dado um certificado, é fácil conferir. Fatorar está em NP: verificar que $p\cdot q = n$ é uma multiplicação.

$$P \subseteq NP$$

Se dá para resolver rápido, dá para verificar rápido. A questão de um milhão de dólares é se a inclusão é estrita.

P versus NP

A crença amplamente compartilhada é que $P \ne NP$, mas não há prova. As implicações de $P = NP$ seriam extraordinárias: criptografia de chave pública desabaria, e encontrar demonstrações matemáticas seria tão fácil quanto verificá-las.

NP-completude

Um problema é NP-difícil quando todo problema de NP se reduz a ele em tempo polinomial. É NP-completo quando é NP-difícil e pertence a NP.

Os NP-completos são os problemas mais difíceis de NP: resolver um deles em tempo polinomial resolveria todos.

Teorema de Cook-Levin (1971). SAT é NP-completo.

Foi o primeiro, e é a partir dele que todos os outros são provados por redução.

Reduções

$A \le_p B$ significa que existe transformação polinomial de instâncias de $A$ em instâncias de $B$ preservando a resposta.

O sentido da redução é a fonte do erro mais comum. Para provar que $B$ é NP-difícil, reduz-se um problema conhecidamente difícil $A$ a $B$ — ou seja, mostra-se que $B$ é pelo menos tão difícil quanto $A$. A direção contrária não prova nada sobre a dificuldade de $B$.

Cadeia clássica de reduções:

$$\text{SAT} \le_p \text{3-SAT} \le_p \text{Clique} \le_p \text{Cobertura por vértices} \le_p \text{Conjunto independente}$$

Problemas NP-completos comuns

Problema	Descrição
SAT / 3-SAT	Satisfatibilidade booleana
Clique	Existe clique de tamanho $k$?
Cobertura por vértices	Existe cobertura de tamanho $k$?
Ciclo hamiltoniano	Existe ciclo que passa por todos os vértices?
Caixeiro viajante (decisão)	Existe rota de custo $\le k$?
Mochila	Existe subconjunto de valor $\ge v$ e peso $\le w$?
Coloração ($k \ge 3$)	O grafo é $k$-colorível?
Partição	Dividir em dois conjuntos de soma igual?
Programação inteira	Existe solução inteira viável?

Vale notar as fronteiras: 2-SAT está em P, mas 3-SAT é NP-completo; 2-coloração está em P, 3-coloração é NP-completa; ciclo euleriano está em P, hamiltoniano é NP-completo. Diferenças mínimas no enunciado atravessam a fronteira.

O que fazer com um problema NP-difícil

Esta é a parte prática, e é o motivo de a classificação importar.

Algoritmos de aproximação. Garantem uma razão em relação ao ótimo. Cobertura por vértices tem aproximação simples de fator 2; o caixeiro viajante métrico tem fator 1,5 (Christofides).

Heurísticas. Sem garantia, mas boas na prática: busca local, algoritmos genéricos, recozimento simulado.

Resolvedores. Resolvedores SAT e ILP modernos lidam com instâncias industriais de milhões de variáveis. A dificuldade de pior caso não impede eficiência nos casos que aparecem na prática — essa distinção é frequentemente esquecida.

Parametrização. Complexidade parametrizada isola a explosão num parâmetro pequeno: cobertura por vértices é resolvível em $O(2^k n)$, tratável quando $k$ é pequeno.

Casos especiais. Muitos problemas NP-difíceis viram polinomiais em grafos de estrutura restrita (planares, cordais, de largura em árvore limitada).

Relaxar o requisito. Talvez não seja preciso o ótimo. Uma solução 5% pior obtida em segundos costuma valer mais que a ótima em semanas.

Outras classes

Classe	Descrição
co-NP	Complementos de problemas de NP
PSPACE	Espaço polinomial; contém NP
EXPTIME	Tempo exponencial; sabidamente $\ne$ P
BPP	Polinomial aleatorizado com erro limitado
BQP	Polinomial quântico
#P	Contagem de soluções

Fatoração está em NP e co-NP, e não se acredita que seja NP-completa — o que é relevante, porque significa que quebrar RSA não implicaria $P = NP$.

Exemplo trabalhado

Por que 3-SAT se reduz a Clique?

Dada uma fórmula com $m$ cláusulas de 3 literais, construa um grafo com um vértice para cada literal de cada cláusula. Ligue dois vértices quando estão em cláusulas diferentes e não são complementares.

A fórmula é satisfatível se e somente se o grafo tem clique de tamanho $m$: um clique escolhe um literal verdadeiro por cláusula, e a ausência de arestas entre complementares garante consistência da atribuição.

A construção é polinomial, e a equivalência vale nos dois sentidos — é isso que uma redução precisa demonstrar.

Erros comuns

• Inverter o sentido da redução.
• Confundir NP-difícil com "impossível". Instâncias reais podem ser fáceis.
• Chamar de NP-completo um problema que não está em NP (otimização, por exemplo, é NP-difícil mas não NP-completa).
• Concluir que NP significa "não polinomial". Significa "não determinístico polinomial".
• Desistir cedo demais. Resolvedores SAT modernos são extraordinariamente eficazes.

Leituras recomendadas

• Sipser, capítulo 7 — P, NP e NP-completude com provas completas.
• Garey e Johnson — o catálogo clássico de problemas NP-completos; ainda a referência para saber se um problema já foi classificado.
• Arora e Barak, Computational Complexity: A Modern Approach — o tratamento moderno; rascunho gratuito online.
• Biere et al., Handbook of Satisfiability — como resolvedores SAT vencem a teoria na prática.

Michael Sipser (2012). Introduction to the Theory of Computation. Cengage Learning. ISBN 9781133187790. Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 9780716710448. Sanjeev Arora and Boaz Barak (2009). Computational Complexity: A Modern Approach. Cambridge University Press. DOI: 10.1017/cbo9780511804090. Armin Biere and Marijn Heule and Hans van Maaren and Toby Walsh (2009). Handbook of Satisfiability. IOS Press. ISBN 9781586039295.

Referências

1. Michael Sipser (2012). Introduction to the Theory of Computation. Cengage Learning.
2. Michael R. Garey; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
3. Sanjeev Arora; Boaz Barak (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
4. Armin Biere; Marijn Heule; Hans van Maaren; Toby Walsh (2009). Handbook of Satisfiability. IOS Press.