Problemas NP-Completos

Computabilidade e Complexidade

Autor

Márcio Nicolau

Data de Publicação

10 de novembro de 2025

Objetivos da Aula

  • Definir redutibilidade em tempo polinomial (\(\leq_p\)).
  • Compreender o conceito de problemas NP-Completos como os “mais difíceis” em NP.
  • Apresentar o Teorema de Cook-Levin e a importância do problema SAT.
  • Aprender a provar que um problema é NP-Completo através de reduções.

Conteúdo

Redefinindo a Redutibilidade para a Complexidade

Na teoria da computabilidade, usamos a redutibilidade para transferir a propriedade de “indecidibilidade”. Agora, na teoria da complexidade, vamos adaptá-la para transferir a propriedade de “dificuldade computacional” (ou “intratabilidade”).

A chave é garantir que a própria redução seja eficiente. Se a transformação de um problema A para um problema B levasse tempo exponencial, ela não nos diria nada útil sobre a dificuldade relativa deles.

ImportanteDefinição: Redutibilidade em Tempo Polinomial

Uma linguagem \(A\) é redutível em tempo polinomial à linguagem \(B\), denotado \(A \leq_p B\), se existe uma função \(f\) computável em tempo polinomial que transforma instâncias de \(A\) em instâncias de \(B\), tal que para toda string \(w\): \[w \in A \iff f(w) \in B\]

Formalmente, existe uma Máquina de Turing determinística \(M\) que computa \(f\) em tempo \(O(n^k)\) para algum \(k \geq 1\), onde \(n = |w|\).

A Lógica: Se \(A \leq_p B\), então \(B\) é pelo menos tão difícil quanto \(A\). Se encontrarmos um algoritmo de tempo polinomial para \(B\), poderemos resolver \(A\) em tempo polinomial também (primeiro executando a redução \(f\), depois o algoritmo para \(B\)).

Propriedades da Redutibilidade Polinomial

A redução polinomial possui propriedades importantes que a tornam uma ferramenta poderosa (Sipser, 2012):

NotaTeorema: Propriedades de ≤ₚ

1. Transitividade: Se \(A \leq_p B\) e \(B \leq_p C\), então \(A \leq_p C\).

Prova: Sejam \(f\) e \(g\) as funções de redução computáveis em tempo polinomial \(p(n)\) e \(q(n)\) respectivamente. A composição \(h(w) = g(f(w))\) é computável em tempo \(p(n) + q(p(n))\), que é polinomial. \(\square\)

2. Preservação de P: Se \(A \leq_p B\) e \(B \in \text{P}\), então \(A \in \text{P}\).

Prova: Se \(M_B\) decide \(B\) em tempo \(q(n)\), construímos \(M_A\) que:

  • Computa \(f(w)\) em tempo \(p(n)\)
  • Executa \(M_B\) em \(f(w)\) em tempo \(q(|f(w)|) \leq q(p(n))\)

O tempo total é \(p(n) + q(p(n))\), que é polinomial. \(\square\)

3. Contrapositiva útil: Se \(A \leq_p B\) e \(A \notin \text{P}\), então \(B \notin \text{P}\).

Isso nos permite usar reduções para provar que problemas são difíceis.

DicaVisualizando a Redução

Uma redução \(A \leq_p B\) pode ser visualizada como um “tradutor” eficiente:

Entrada w → [Redução f] → f(w) → [Algoritmo para B] → SIM/NÃO
            (tempo poli)         (tempo desconhecido)

Se w ∈ A  ⟺  f(w) ∈ B

A redução preserva a resposta: instâncias “sim” de \(A\) são mapeadas para instâncias “sim” de \(B\), e instâncias “não” de \(A\) são mapeadas para instâncias “não” de \(B\).

NP-Completude: Os Problemas Mais Difíceis em NP

Dentro da vasta classe NP, alguns problemas se destacam. Eles são os “chefões finais” de NP. Se conseguirmos resolver qualquer um deles de forma eficiente, conseguiremos resolver todos os problemas em NP de forma eficiente.

NotaDefinição: Problemas NP-Completos (NPC)

Uma linguagem \(L\) é NP-Completa se satisfaz duas condições:

  1. \(L\) está em NP (\(L \in \text{NP}\)).
  2. Toda outra linguagem em NP é redutível em tempo polinomial a \(L\) (\(\forall A \in \text{NP}, A \leq_p L\)).

Quando um problema satisfaz apenas a condição (2), dizemos que ele é NP-Difícil (NP-Hard).

Um problema NP-Completo (NPC) é, portanto, um problema em NP que é pelo menos tão difícil quanto qualquer outro problema em NP.

ImportanteTeorema Fundamental da NP-Completude

Se qualquer problema NP-Completo está em P, então P = NP.

Prova: Seja \(L\) um problema NP-Completo em P. Para qualquer \(A \in \text{NP}\):

  • Por definição de NP-Completude: \(A \leq_p L\)
  • Como \(L \in \text{P}\), pela propriedade de preservação: \(A \in \text{P}\)
  • Como \(A\) era arbitrário: \(\text{NP} \subseteq \text{P}\)
  • Já sabemos que \(\text{P} \subseteq \text{NP}\)
  • Portanto: \(\text{P} = \text{NP}\) \(\square\)

Contrapositiva: Se P ≠ NP, então nenhum problema NP-Completo está em P!

Este teorema explica por que os problemas NP-Completos são tão importantes: eles são a “fronteira” entre P e NP.

O Teorema de Cook-Levin: O Primeiro Problema NP-Completo

A definição de NP-Completude parece criar um problema de “ovo e galinha”: como provar que o primeiro problema é NP-Completo, se não temos nenhum outro problema NPC para reduzir a partir dele?

A resposta veio em 1971 com o trabalho de Stephen Cook e Leonid Levin.

ImportanteTeorema de Cook-Levin

O problema da Satisfatibilidade Booleana (SAT) é NP-Completo. (Sipser, 2012, p. 312)

Problema SAT: Dada uma fórmula booleana \(\phi\) com variáveis, conectivos ∧ (E), ∨ (OU) e ¬ (NÃO) (ex: \((x_1 \lor \neg x_2) \land (x_2 \lor x_3)\)), existe uma atribuição de Verdadeiro/Falso para as variáveis que torna a fórmula inteira Verdadeira?

Formalmente: SAT = {\(\langle \phi \rangle\) | \(\phi\) é uma fórmula booleana satisfazível}

Esboço da Prova do Teorema de Cook-Levin

A prova é técnica, mas a ideia central é elegante e poderosa (Sipser, 2012):

Objetivo: Mostrar que para qualquer linguagem \(L \in \text{NP}\), temos \(L \leq_p \text{SAT}\).

Estratégia:

  1. Como \(L \in \text{NP}\), existe uma MTN \(N\) que decide \(L\) em tempo polinomial \(n^k\)
  2. Para uma entrada \(w\), construímos uma fórmula booleana \(\phi\) que “simula” a computação de \(N\) em \(w\)
  3. A fórmula \(\phi\) é satisfazível ⟺ \(N\) aceita \(w\) ⟺ \(w \in L\)

Construção da Fórmula \(\phi\):

A fórmula codifica a tabela de computação de \(N\) em \(w\) usando variáveis booleanas:

  • \(x_{i,j,s}\) = “na configuração \(i\) (passo de tempo), a célula \(j\) contém o símbolo \(s\)”
  • \(x_{i,q}\) = “na configuração \(i\), a máquina está no estado \(q\)”

A fórmula \(\phi\) é a conjunção de subcláusulas que garantem:

  1. \(\phi_{\text{cell}}\): Cada célula contém exatamente um símbolo em cada momento
  2. \(\phi_{\text{start}}\): A configuração inicial é correta (contém \(w\))
  3. \(\phi_{\text{move}}\): Cada configuração segue validamente da anterior (seguindo a função de transição de \(N\))
  4. \(\phi_{\text{accept}}\): Alguma configuração é de aceitação

Por que funciona:

  • Se \(w \in L\): existe um ramo de aceitação em \(N\), que corresponde a uma atribuição satisfazível para \(\phi\)
  • Se \(w \notin L\): nenhum ramo aceita, logo \(\phi\) é insatisfazível
  • A construção leva tempo polinomial: \(O(n^{2k})\) variáveis e cláusulas
NotaTamanho da Fórmula

Para uma entrada de tamanho \(n\) e MTN com tempo \(n^k\):

  • Número de configurações: \(O(n^k)\)
  • Tamanho de cada configuração: \(O(n^k)\)
  • Número de variáveis: \(O(n^{2k})\)
  • Tamanho da fórmula: \(O(n^{2k})\)

Tudo polinomial! \(\square\)

A Genialidade da Prova: A prova mostra que, para qualquer problema em NP, a computação de sua Máquina de Turing Não-Determinística pode ser traduzida, em tempo polinomial, em uma fórmula SAT. Essa fórmula será satisfatível se, e somente se, a máquina aceitar a entrada. Isso estabelece que SAT é o “problema original” ao qual todos os outros em NP podem ser reduzidos.

Provando que Outros Problemas são NP-Completos

Uma vez que temos o SAT como nosso ponto de partida, a receita para provar que um novo problema \(L\) é NP-Completo se torna muito mais simples:

  1. Mostre que \(L \in \text{NP}\): Geralmente, esta é a parte fácil. Basta mostrar que, dada uma solução (um certificado), podemos verificá-la rapidamente (em tempo polinomial).
  2. Mostre que \(L\) é NP-Difícil: Para isso, escolha um problema \(S\) que você já sabe que é NP-Completo (como SAT, 3-SAT, SUBSET-SUM, etc.) e construa uma redução em tempo polinomial \(S \leq_p L\).

Exemplo de Redução 1: SAT ≤ₚ 3-SAT

Um dos exemplos mais importantes é mostrar que 3-SAT (uma versão restrita de SAT) também é NP-Completo (Sipser, 2012).

NotaDefinição: 3-SAT

3-SAT = {\(\langle \phi \rangle\) | \(\phi\) é uma fórmula booleana satisfazível na forma normal conjuntiva (CNF) onde cada cláusula tem exatamente 3 literais}

Exemplo: \((x_1 \lor x_2 \lor \neg x_3) \land (\neg x_1 \lor x_2 \lor x_4) \land (x_3 \lor \neg x_4 \lor x_1)\)

Prova de NP-Completude de 3-SAT:

Passo 1: Mostrar que 3-SAT ∈ NP

  • Certificado: Uma atribuição de valores às variáveis
  • Verificador: Avalia cada cláusula (tempo linear)
  • Portanto, 3-SAT ∈ NP ✓

Passo 2: Mostrar SAT ≤ₚ 3-SAT

Dada uma fórmula SAT arbitrária \(\phi\), construímos \(\phi'\) em 3-CNF:

  1. Converter para CNF (já conhecida, tempo polinomial)

  2. Ajustar cláusulas para ter exatamente 3 literais:

    • Cláusula com 1 literal \((l_1)\): substituir por \((l_1 \lor y \lor z) \land (l_1 \lor y \lor \neg z) \land (l_1 \lor \neg y \lor z) \land (l_1 \lor \neg y \lor \neg z)\) onde \(y, z\) são novas variáveis
    • Cláusula com 2 literais \((l_1 \lor l_2)\): substituir por \((l_1 \lor l_2 \lor y) \land (l_1 \lor l_2 \lor \neg y)\)
    • Cláusula com 3 literais: manter como está
    • Cláusula com \(k > 3\) literais \((l_1 \lor l_2 \lor \ldots \lor l_k)\): substituir por \((l_1 \lor l_2 \lor y_1) \land (\neg y_1 \lor l_3 \lor y_2) \land \ldots \land (\neg y_{k-3} \lor l_{k-1} \lor l_k)\)

Esta construção preserva satisfazibilidade e leva tempo polinomial. Portanto, SAT ≤ₚ 3-SAT ✓

Como SAT é NP-Completo e SAT ≤ₚ 3-SAT, concluímos que 3-SAT é NP-Completo. \(\square\)

Exemplo de Redução 2: 3-SAT ≤ₚ CLIQUE

Agora vamos mostrar que o problema CLIQUE é NP-Completo reduzindo de 3-SAT (Sipser, 2012).

NotaLembrando: CLIQUE

CLIQUE = {\(\langle G, k \rangle\) | \(G\) é um grafo não-direcionado contendo uma \(k\)-clique}

Uma \(k\)-clique é um subconjunto de \(k\) vértices onde cada par está conectado por uma aresta.

Prova de NP-Completude de CLIQUE:

Passo 1: CLIQUE ∈ NP (já vimos na aula anterior) ✓

Passo 2: 3-SAT ≤ₚ CLIQUE

Ideia: Dada uma fórmula 3-CNF \(\phi\) com \(k\) cláusulas, construímos um grafo \(G\) tal que:

  • \(\phi\) é satisfazível ⟺ \(G\) tem uma \(k\)-clique

Construção:

  1. Para cada cláusula \((l_1 \lor l_2 \lor l_3)\), criar 3 vértices (um para cada literal)

  2. Conectar dois vértices com aresta se:

    • Estão em cláusulas diferentes, E
    • Não são contraditórios (ex: \(x\) e \(\neg x\))

Exemplo: Para \(\phi = (x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor \neg x_2 \lor \neg x_3) \land (x_1 \lor x_2 \lor \neg x_3)\)

graph LR
    subgraph "Cláusula 1"
        A1["x₁"]
        A2["x₂"]
        A3["x₃"]
    end

    subgraph "Cláusula 2"
        B1["¬x₁"]
        B2["¬x₂"]
        B3["¬x₃"]
    end

    subgraph "Cláusula 3"
        C1["x₁"]
        C2["x₂"]
        C3["¬x₃"]
    end

    A2 -.-> B1
    A2 -.-> B3
    A3 -.-> B1
    A3 -.-> B2

    A2 -.-> C1
    A2 -.-> C3
    A3 -.-> C1

    B1 -.-> C2
    B1 -.-> C3
    B2 -.-> C1
    B2 -.-> C3

    style A1 fill:#ffcccc
    style A2 fill:#ccffcc
    style A3 fill:#ccccff
    style B1 fill:#ffcccc
    style B2 fill:#ccffcc
    style B3 fill:#ccccff
    style C1 fill:#ffcccc
    style C2 fill:#ccffcc
    style C3 fill:#ccccff
Figura 1: Redução de 3-SAT para CLIQUE. Cada “tripla” representa uma cláusula.

Correção:

  • Se \(\phi\) é satisfazível: escolha um literal verdadeiro de cada cláusula → esses \(k\) vértices formam uma \(k\)-clique
  • Se \(G\) tem \(k\)-clique: atribua verdadeiro aos literais correspondentes → todas as \(k\) cláusulas ficam verdadeiras

A construção leva tempo \(O(k^2)\), polinomial. Portanto, 3-SAT ≤ₚ CLIQUE ✓

Como 3-SAT é NP-Completo e 3-SAT ≤ₚ CLIQUE, concluímos que CLIQUE é NP-Completo. \(\square\)

Diagrama: A Árvore de Reduções NP-Completas

graph TD
    SAT["<b>SAT</b><br/>(Cook-Levin 1971)"]

    TSAT["<b>3-SAT</b><br/>(3 literais por cláusula)"]
    CLIQUE["<b>CLIQUE</b><br/>(subgrafo completo)"]
    VERTEX["<b>VERTEX-COVER</b><br/>(cobertura de vértices)"]
    INDSET["<b>INDEPENDENT-SET</b><br/>(conjunto independente)"]
    HAMPATH["<b>HAMPATH</b><br/>(caminho hamiltoniano)"]
    TSP["<b>TSP</b><br/>(caixeiro viajante)"]
    SUBSETSUM["<b>SUBSET-SUM</b><br/>(soma de subconjunto)"]
    PARTITION["<b>PARTITION</b><br/>(partição balanceada)"]

    SAT -->|redução| TSAT
    TSAT -->|redução| CLIQUE
    TSAT -->|redução| VERTEX
    CLIQUE -->|complemento| INDSET
    TSAT -->|redução| HAMPATH
    HAMPATH -->|redução| TSP
    TSAT -->|redução| SUBSETSUM
    SUBSETSUM -->|redução| PARTITION

    style SAT fill:#ff9999,stroke:#b71c1c,stroke-width:3px
    style TSAT fill:#ffcccc
    style CLIQUE fill:#ffe6e6
    style VERTEX fill:#ffe6e6
    style INDSET fill:#ffe6e6
    style HAMPATH fill:#ffe6e6
    style TSP fill:#ffe6e6
    style SUBSETSUM fill:#ffe6e6
    style PARTITION fill:#ffe6e6
Figura 2: A NP-Completude se espalha a partir de SAT. As setas mostram reduções (A → B significa A ≤ₚ B).
NotaObservações sobre o Diagrama
  • SAT é o problema fundamental (Teorema de Cook-Levin)
  • 3-SAT é frequentemente usado como ponto de partida para outras reduções
  • Todos os problemas mostrados são NP-Completos
  • Conhecer essas reduções clássicas permite provar NP-Completude de novos problemas
  • Existem milhares de problemas NP-Completos conhecidos!

O Significado Prático da NP-Completude

Se você está trabalhando em um problema e descobre que ele é NP-Completo, isso tem implicações imediatas:

  1. Pare de procurar por um algoritmo rápido e exato: É extremamente improvável que você encontre um. Se você o fizesse, teria provado que P = NP e ganharia um milhão de dólares.

  2. Mude sua abordagem: Em vez de uma solução perfeita e rápida, concentre-se em:

    • Algoritmos de Aproximação: Encontram uma solução que é “boa o suficiente”, perto da ótima.
    • Heurísticas: Algoritmos que funcionam bem na maioria dos casos do “mundo real”, mas sem garantias teóricas.
    • Algoritmos Exponenciais para Instâncias Pequenas: Se suas entradas são sempre pequenas, uma solução \(O(2^n)\) pode ser aceitável.

Exemplos em Python: Problemas NP-Completos

Exemplo 1: O Problema CLIQUE

CLIQUE: Dado um grafo \(G\) e um inteiro \(k\), existe um subconjunto de \(k\) vértices em \(G\) onde cada vértice está conectado a todos os outros (formando um “clique” de tamanho \(k\))?

Este problema é um exemplo clássico de NPC.

Resolvedor de força bruta para CLIQUE 
import itertools

def verificar_clique(grafo, certificado):
    """
    Verificador para CLIQUE (tempo polinomial).
    Verifica se o certificado forma um clique.
    """
    k = len(certificado)

    # Verifica se todos os pares estão conectados
    for v1, v2 in itertools.combinations(certificado, 2):
        if v2 not in grafo.get(v1, []) or v1 not in grafo.get(v2, []):
            return False

    return True

def resolver_clique_forca_bruta(grafo, k):
    """
    Resolve o problema CLIQUE por força bruta.
    Testa todos os subconjuntos de k vértices.
    Complexidade: O(C(n,k) * k^2) ≈ O(n^k) - EXPONENCIAL!
    """
    vertices = list(grafo.keys())
    n = len(vertices)

    if k > n:
        return None

    # Gera todas as combinações de k vértices
    num_combinacoes = 0
    for combinacao in itertools.combinations(vertices, k):
        num_combinacoes += 1
        if verificar_clique(grafo, combinacao):
            print(f"Testadas {num_combinacoes} combinações")
            return combinacao

    print(f"Testadas todas as {num_combinacoes} combinações")
    return None

# --- Exemplo de Uso ---
# Grafo representado como uma lista de adjacência
meu_grafo = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D', 'E'],
    'D': ['A', 'B', 'C'],
    'E': ['C']
}
k = 4

print("=== CLIQUE: Buscando um Clique ===\n")
print(f"Grafo: {meu_grafo}")
print(f"Tamanho do clique procurado: {k}\n")

print(f"--- Resolvendo (força bruta) ---")
clique_encontrado = resolver_clique_forca_bruta(meu_grafo, k)
if clique_encontrado:
    print(f"Clique de tamanho {k} encontrado: {clique_encontrado}")
else:
    print(f"Nenhum clique de tamanho {k} foi encontrado.")

print("\n--- Verificando um certificado ---")
certificado = ['A', 'B', 'C', 'D']
resultado = verificar_clique(meu_grafo, certificado)
print(f"O conjunto {certificado} forma um clique? {resultado}")
=== CLIQUE: Buscando um Clique ===

Grafo: {'A': ['B', 'C', 'D'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B', 'D', 'E'], 'D': ['A', 'B', 'C'], 'E': ['C']}
Tamanho do clique procurado: 4

--- Resolvendo (força bruta) ---
Testadas 1 combinações
Clique de tamanho 4 encontrado: ('A', 'B', 'C', 'D')

--- Verificando um certificado ---
O conjunto ['A', 'B', 'C', 'D'] forma um clique? True

Exemplo 2: 3-SAT

Vamos implementar um resolvedor de força bruta para 3-SAT:

Resolvedor e verificador para 3-SAT 
def avaliar_clausula(clausula, atribuicao):
    """
    Avalia uma cláusula (disjunção de literais).
    clausula: lista de tuplas (variável, negado)
    Ex: [(0, False), (1, True), (2, False)] representa (x0 ∨ ¬x1 ∨ x2)
    """
    for var, negado in clausula:
        valor = atribuicao[var]
        if negado:
            valor = not valor
        if valor:  # Se algum literal é verdadeiro, a cláusula é verdadeira
            return True
    return False

def verificar_3sat(formula, atribuicao):
    """
    Verificador para 3-SAT (tempo polinomial).
    Verifica se a atribuição satisfaz todas as cláusulas.
    """
    return all(avaliar_clausula(clausula, atribuicao) for clausula in formula)

def resolver_3sat_forca_bruta(formula, num_variaveis):
    """
    Resolve 3-SAT por força bruta.
    Testa todas as 2^n atribuições possíveis.
    Complexidade: O(2^n * m) onde n = variáveis, m = cláusulas - EXPONENCIAL!
    """
    # Testa todas as atribuições possíveis (2^n)
    for i in range(1 << num_variaveis):
        # Converte o número i em uma atribuição binária
        atribuicao = [(i >> j) & 1 for j in range(num_variaveis)]

        if verificar_3sat(formula, atribuicao):
            return atribuicao

    return None

# --- Exemplo de Uso ---
# Fórmula: (x0 ∨ x1 ∨ x2) ∧ (¬x0 ∨ ¬x1 ∨ ¬x2) ∧ (x0 ∨ ¬x1 ∨ x2)
formula_3sat = [
    [(0, False), (1, False), (2, False)],  # (x0 ∨ x1 ∨ x2)
    [(0, True), (1, True), (2, True)],      # (¬x0 ∨ ¬x1 ∨ ¬x2)
    [(0, False), (1, True), (2, False)]     # (x0 ∨ ¬x1 ∨ x2)
]
num_vars = 3

print("\n=== 3-SAT: Satisfatibilidade ===\n")
print("Fórmula: (x0 ∨ x1 ∨ x2) ∧ (¬x0 ∨ ¬x1 ∨ ¬x2) ∧ (x0 ∨ ¬x1 ∨ x2)\n")

print("--- Resolvendo (força bruta) ---")
solucao = resolver_3sat_forca_bruta(formula_3sat, num_vars)
if solucao:
    print(f"Fórmula SAT satisfazível!")
    print(f"Atribuição: x0={solucao[0]}, x1={solucao[1]}, x2={solucao[2]}")
else:
    print("Fórmula UNSAT (insatisfazível)")

print("\n--- Verificando uma atribuição ---")
atrib_teste = [1, 0, 1]  # x0=True, x1=False, x2=True
resultado = verificar_3sat(formula_3sat, atrib_teste)
print(f"Atribuição {atrib_teste} satisfaz a fórmula? {resultado}")

print("\n--- Análise de Complexidade ---")
print(f"Número de variáveis: {num_vars}")
print(f"Número de cláusulas: {len(formula_3sat)}")
print(f"Atribuições possíveis: 2^{num_vars} = {2**num_vars}")
print(f"Tempo do verificador: O(m) = O({len(formula_3sat)})")
print(f"Tempo do resolvedor força-bruta: O(2^n * m) = O({2**num_vars * len(formula_3sat)})")

=== 3-SAT: Satisfatibilidade ===

Fórmula: (x0 ∨ x1 ∨ x2) ∧ (¬x0 ∨ ¬x1 ∨ ¬x2) ∧ (x0 ∨ ¬x1 ∨ x2)

--- Resolvendo (força bruta) ---
Fórmula SAT satisfazível!
Atribuição: x0=1, x1=0, x2=0

--- Verificando uma atribuição ---
Atribuição [1, 0, 1] satisfaz a fórmula? True

--- Análise de Complexidade ---
Número de variáveis: 3
Número de cláusulas: 3
Atribuições possíveis: 2^3 = 8
Tempo do verificador: O(m) = O(3)
Tempo do resolvedor força-bruta: O(2^n * m) = O(24)
AvisoA Explosão Exponencial

Observe a diferença dramática:

  • Verificar uma solução: O(m) - linear no número de cláusulas
  • Encontrar uma solução: O(2^n · m) - exponencial no número de variáveis

Para n=50 variáveis: 2^50 ≈ 10^15 atribuições para testar!

O código acima usa força bruta, que é ineficiente. A NP-Completude desses problemas sugere que não existe um algoritmo significativamente melhor (em tempo polinomial).

Exercícios de Verificação

NotaAtividade Prática

  1. Definições: Qual a diferença entre um problema ser NP e ser NP-Completo? Um problema pode ser NP-Completo mas não ser NP?

  2. Prova de NP-Completude: Você quer provar que um novo problema, PROB_X, é NP-Completo. Você já demonstrou que PROB_X está em NP. Agora, você constrói uma redução \(PROB\_X \leq_p \text{SAT}\). Esta redução ajuda a completar sua prova? Se não, o que você deveria ter feito?

  3. Análise de Problema: Considere o problema COBERTURA DE VÉRTICES (VERTEX-COVER): “Dado um grafo \(G\) e um inteiro \(k\), existe um subconjunto de \(k\) vértices tal que toda aresta do grafo toca em pelo menos um desses vértices?”. Descreva por que este problema está em NP.

  4. Transitividade: Se sabemos que 3-SAT é NP-Completo e construímos uma redução 3-SAT ≤ₚ HAMPATH, o que podemos concluir sobre HAMPATH (assumindo que já mostramos HAMPATH ∈ NP)?

  5. Redução Reversa: Suponha que você está tentando provar que um problema L é NP-Completo. Você mostra que L ∈ NP e depois constrói uma redução L ≤ₚ 3-SAT. Isso prova que L é NP-Completo? Por quê?

  6. Complemento: Se um problema L é NP-Completo, o que podemos dizer sobre seu complemento \(\overline{L}\)? Ele também é NP-Completo?

  7. Construção de Redução: Esboce uma ideia de como construir uma redução de CLIQUE para INDEPENDENT-SET. (Dica: pense no grafo complemento)

  1. Diferença entre NP e NPC:

    • NP é uma classe de problemas que possuem uma verificação rápida (em tempo polinomial).
    • NP-Completo (NPC) é uma subclasse de NP. Problemas NPC não são apenas “verificáveis” (a primeira condição, estarem em NP), mas também são os “mais difíceis” de toda a classe NP (a segunda condição, de que todo outro problema em NP se reduz a eles).
    • Não, um problema não pode ser NP-Completo sem ser NP. A primeira regra para ser NPC é pertencer à classe NP.
    • Diagrama: NPC = NP ∩ NP-Difícil

  2. Erro na Redução: A redução \(PROB\_X \leq_p \text{SAT}\) não ajuda a provar que PROB_X é NP-Completo. Esta redução mostra que PROB_X não é mais difícil que SAT (na verdade, mostra que PROB_X ∈ P se SAT ∈ P). Para provar que PROB_X é NP-Difícil (a segunda parte da prova de NPC), você precisa fazer a redução na direção oposta: encontrar um problema conhecido por ser NP-Completo, como SAT, e provar que \(\text{SAT} \leq_p PROB\_X\). Isso mostraria que PROB_X é pelo menos tão difícil quanto SAT.

  3. VERTEX-COVER está em NP: O problema está em NP porque podemos verificar uma solução proposta de forma eficiente.

    • Certificado: Um subconjunto \(C \subseteq V\) de \(k\) vértices
    • Verificador: Um algoritmo que recebe o grafo \(G = (V, E)\) e o certificado \(C\):
      1. Verifica se \(|C| \leq k\)
      2. Para cada aresta \((u, v) \in E\), verifica se \(u \in C\) ou \(v \in C\)
      3. Aceita se todas as arestas são cobertas
    • Tempo: \(O(|E|)\) - linear no número de arestas
    • Este processo é polinomial, logo VERTEX-COVER ∈ NP ✓

  4. Transitividade e HAMPATH:

    • Sabemos que 3-SAT é NP-Completo
    • Construímos 3-SAT ≤ₚ HAMPATH
    • Já sabemos que HAMPATH ∈ NP
    • Conclusão: HAMPATH é NP-Completo!
    • Justificativa: Por transitividade, se todo problema em NP se reduz a 3-SAT, e 3-SAT se reduz a HAMPATH, então todo problema em NP se reduz a HAMPATH. Como HAMPATH ∈ NP, ele satisfaz ambas as condições de NP-Completude.

  5. Redução Reversa NÃO funciona:

    • NÃO, isso não prova que L é NP-Completo
    • A redução L ≤ₚ 3-SAT mostra apenas que L não é mais difícil que 3-SAT
    • Na verdade, todo problema em P também se reduz a 3-SAT!
    • O que precisamos: Mostrar 3-SAT ≤ₚ L (ou qualquer problema NPC ≤ₚ L)
    • Analogia: “Provar que você é mais forte que o campeão não significa provar que o campeão é mais fraco que você”

  6. Complemento de NP-Completo:

    • Se L é NP-Completo, então \(\overline{L}\) está em co-NP
    • \(\overline{L}\) é co-NP-Completo (o mais difícil problema em co-NP)
    • Mas: Não sabemos se \(\overline{L}\) é NP-Completo!
    • Se conseguíssemos provar que algum problema co-NP-Completo também é NP-Completo, teríamos NP = co-NP (questão em aberto!)
    • Exemplo: SAT é NP-Completo, mas UNSAT (seu complemento) é co-NP-Completo

  7. CLIQUE ≤ₚ INDEPENDENT-SET: Ideia da redução:

    • Dado \(\langle G, k \rangle\) para CLIQUE, construir \(\langle G', k' \rangle\) para INDEPENDENT-SET
    • Construção:
      • \(G' = \overline{G}\) (grafo complemento: arestas viram não-arestas e vice-versa)
      • \(k' = k\)
    • Correção: \(G\) tem \(k\)-clique ⟺ \(\overline{G}\) tem \(k\)-independent-set
    • Justificativa: Vértices que formam clique em \(G\) (todos conectados) formam conjunto independente em \(\overline{G}\) (nenhum conectado)
    • Tempo: \(O(n^2)\) para construir o grafo complemento - polinomial!
    • Logo, CLIQUE ≤ₚ INDEPENDENT-SET ✓

Aplicações Práticas e Perspectivas

A teoria da NP-Completude não é apenas matemática abstrata - ela tem profundas implicações práticas.

Problemas NP-Completos no Mundo Real

Milhares de problemas práticos importantes são NP-Completos (Sipser, 2012):

  1. Otimização de Recursos
    • Alocação de tarefas a processadores
    • Escalonamento de horários (escola, aeroportos)
    • Empacotamento de itens (bin packing)
  2. Design de Circuitos
    • Roteamento de circuitos VLSI
    • Verificação de circuitos
  3. Bioinformática
    • Alinhamento de sequências de DNA
    • Dobramento de proteínas
  4. Redes e Logística
    • Roteamento de veículos
    • Planejamento de rotas de entrega

Lidando com NP-Completude na Prática

Quando você identifica que seu problema é NP-Completo, você tem várias opções (Sipser, 2012):

DicaEstratégias Práticas
  1. Algoritmos de Aproximação
    • Garantem solução “próxima” da ótima em tempo polinomial
    • Ex: Algoritmo 2-aproximação para VERTEX-COVER
  2. Heurísticas e Metaheurísticas
    • Algoritmos genéticos, simulated annealing, busca tabu
    • Funcionam bem na prática, mas sem garantias teóricas
  3. Casos Especiais
    • Muitos problemas NP-Completos têm subclasses tratáveis
    • Ex: 2-SAT está em P (mas 3-SAT é NP-Completo!)
  4. Algoritmos Parametrizados
    • Exponencial em um parâmetro, polinomial nos outros
    • Ex: VERTEX-COVER é O(2^k · n) usando kernel
  5. Instâncias Pequenas
    • Se suas entradas são sempre pequenas (n ≤ 30), exponencial pode ser aceitável
    • Técnicas: backtracking inteligente, programação dinâmica
  6. Aproximação Física
    • Computação quântica, computação por DNA
    • Ainda em pesquisa!

Contexto Histórico e Impacto

ImportanteMomentos Históricos
  • 1971: Stephen Cook publica o Teorema de Cook-Levin
  • 1972: Richard Karp identifica 21 problemas NP-Completos clássicos
  • Anos 1970-1980: Explosão de descobertas - milhares de problemas NP-Completos
  • Hoje: Mais de 10.000 problemas NP-Completos conhecidos!

O trabalho de Karp (1972) foi fundamental porque mostrou que NP-Completude não é uma curiosidade matemática, mas aparece em problemas práticos de todas as áreas.

NotaLista de Karp (1972)

Alguns dos 21 problemas originais de Karp:

  1. SAT e 3-SAT
  2. CLIQUE
  3. VERTEX-COVER
  4. HAMPATH e TSP
  5. SUBSET-SUM
  6. PARTITION
  7. Graph Coloring
  8. Knapsack
  9. Job Scheduling
  10. … e outros

Todos esses problemas práticos compartilham a mesma dificuldade fundamental!

O Futuro da NP-Completude

Perguntas ainda em aberto:

  • P vs NP permanece sem resposta
  • Novos paradigmas (computação quântica) podem ajudar?
  • Teorias de complexidade avançadas (PH, PSPACE, etc.)

Impacto contínuo:

  • Toda nova área da computação encontra problemas NP-Completos
  • Machine Learning: treinamento ótimo de redes neurais é NP-Completo
  • Blockchain: mineração de criptomoedas usa problemas computacionalmente difíceis
  • Verificação formal: muitos problemas de verificação são NP-Completos

A teoria da NP-Completude nos ensina limites fundamentais do que podemos computar eficientemente, guiando o desenvolvimento de algoritmos práticos e teorias de complexidade mais profundas.

Referências Bibliográficas

SIPSER, Michael. Introdução à Teoria da Computação. 3. ed. São Paulo, Brasil: Cengage Learning, 2012.