Classes de Complexidade de Tempo: P e NP

Computabilidade e Complexidade

Autor

Márcio Nicolau

Data de Publicação

3 de novembro de 2025

Objetivos da Aula

Definir formalmente a classe P de problemas resolvíveis em tempo polinomial.
Definir a classe NP usando a noção de verificação em tempo polinomial.
Distinguir claramente entre resolver um problema e verificar uma solução.
Apresentar a questão P vs. NP como o problema em aberto mais importante da ciência da computação.

Conteúdo

Revisitando a Classe P

Na aula anterior, introduzimos a Classe P como nossa formalização para problemas “eficientemente solucionáveis” ou “tratáveis”.

Definição Essencial: Classe P

P é a classe de linguagens (problemas de decisão) que podem ser decididas por uma Máquina de Turing determinística em tempo polinomial.

Formalmente: \[ \text{P} = \bigcup_{k \geq 1} \text{TIME}(n^k) \]

Em termos simples: se um problema está em P, existe um algoritmo para ele que roda em tempo $O(n^k)$ para alguma constante $k$, onde $n$ é o tamanho da entrada.

Problemas em P são ótimos de se ter. Encontrar um caminho em um grafo, ordenar uma lista, multiplicar matrizes — todos eles têm algoritmos eficientes que podemos executar em computadores reais.

Exemplos Clássicos de Problemas em P

Vejamos alguns exemplos fundamentais de problemas que estão em P, conforme apresentados em (Sipser, 2012):

PATH = {$\langle G, s, t \rangle$ | $G$ é um grafo direcionado que contém um caminho direcionado de $s$ para $t$}
- Algoritmo: Busca em largura (BFS) ou busca em profundidade (DFS)
- Complexidade: $O(m + n)$ onde $m$ é o número de arestas e $n$ o número de vértices
RELPRIME = {$\langle x, y \rangle$ | $x$ e $y$ são inteiros relativamente primos}
- Algoritmo: Algoritmo de Euclides para calcular o MDC
- Complexidade: $O(n)$ onde $n$ é o número de bits na entrada
PRIMES = {$\langle p \rangle$ | $p$ é um número primo}
- Algoritmo: Teste de primalidade AKS (Agrawal-Kayal-Saxena)
- Complexidade: $O((\log n)^{12})$ - polinomial no tamanho da entrada (Sipser, 2012)

Por que tempo polinomial?

A escolha de tempo polinomial como definição de “eficiente” não é arbitrária:

Robustez: A classe P é invariante sob diferentes modelos de computação razoáveis
Fechamento: P é fechada sob operações naturais como composição
Correspondência prática: Na prática, algoritmos polinomiais tendem a ser viáveis, enquanto algoritmos exponenciais não são
Distinção clara: A diferença entre $n^{100}$ e $2^n$ é significativa conforme $n$ cresce

A Classe NP: O Poder da Verificação

Agora, vamos considerar um tipo diferente de problema. Imagine que você está tentando resolver um quebra-cabeça Sudoku.

Resolver o Sudoku do zero: Pode ser muito difícil. Você pode precisar tentar várias combinações, voltar atrás (backtracking), e isso pode levar muito tempo.
Verificar uma solução completa: Se alguém lhe entregar um Sudoku preenchido e disser “aqui está a solução”, é extremamente fácil e rápido verificar se a solução está correta. Você só precisa checar cada linha, coluna e bloco para garantir que não há números repetidos.

Essa distinção entre “dificil de resolver, mas fácil de verificar” é a essência da Classe NP.

Definição Formal: Classe NP

NP é a classe de linguagens que possuem verificadores em tempo polinomial.

Uma linguagem $L$ está em NP se existe um algoritmo $V$ (o verificador) e uma constante $k$ tal que: \[ w \in L \iff \exists c, |c| \le |w|^k, \text{ tal que } V(\langle w, c \rangle) \text{ aceita em tempo polinomial.} \]

Onde:

$w$ é a instância do problema (o tabuleiro Sudoku vazio).
$c$ é o “certificado” ou “testemunha” (o Sudoku preenchido).
$V$ é o verificador que, dado o problema e o certificado, confirma a solução rapidamente.

NP significa Nondeterministic Polynomial Time (Tempo Polinomial Não-Determinístico). Uma definição alternativa e equivalente é que NP é a classe de problemas que podem ser resolvidos em tempo polinomial por uma Máquina de Turing Não-Determinística. A NTM “adivinha” magicamente o certificado correto e depois o verifica.

Definição Alternativa: NP via Máquinas de Turing Não-Determinísticas

Definição Alternativa de NP

Uma linguagem $L$ está em NP se existe uma Máquina de Turing Não-Determinística (MTN) que decide $L$ em tempo polinomial.

Formalmente: \[ \text{NP} = \bigcup_{k \geq 1} \text{NTIME}(n^k) \]

onde NTIME$(t(n))$ é a classe de linguagens decidíveis por uma MTN em tempo $O(t(n))$.

Teorema (Sipser, 2012): As duas definições de NP são equivalentes: 1. Linguagens com verificadores em tempo polinomial 2. Linguagens decidíveis por MTN em tempo polinomial

Prova (Esboço):

($\Rightarrow$) Se $L$ tem verificador $V$ em tempo $O(n^k)$, construímos uma MTN $N$ que:
1. Não-deterministicamente “adivinha” um certificado $c$ de tamanho $\le n^k$
2. Executa $V$ deterministicamente em $\langle w, c \rangle$
3. Aceita se $V$ aceita
O tempo total é polinomial.
($\Leftarrow$) Se $L$ é decidida por MTN $N$ em tempo $O(n^k)$, construímos um verificador $V$ que:
1. Recebe entrada $\langle w, c \rangle$ onde $c$ codifica as escolhas não-determinísticas de $N$
2. Simula $N$ em $w$ seguindo as escolhas especificadas em $c$
3. Aceita se a simulação aceita
O tempo de verificação é polinomial. $\square$

Exemplos Clássicos de Problemas em NP

Vejamos exemplos detalhados conforme (Sipser, 2012):

HAMPATH = {$\langle G, s, t \rangle$ | $G$ é um grafo direcionado contendo um caminho hamiltoniano de $s$ para $t$}
- Certificado: Uma sequência de vértices $v_1, v_2, \ldots, v_n$
- Verificador: Verifica que:
  - $v_1 = s$ e $v_n = t$
  - Todos os vértices são distintos
  - $(v_i, v_{i+1})$ é uma aresta para todo $i$
- Tempo: $O(n^2)$ onde $n$ é o número de vértices
CLIQUE = {$\langle G, k \rangle$ | $G$ é um grafo não-direcionado contendo uma $k$-clique}
- Certificado: Um subconjunto $C$ de $k$ vértices
- Verificador: Verifica que todo par de vértices em $C$ está conectado por uma aresta
- Tempo: $O(k^2)$
SUBSET-SUM = {$\langle S, t \rangle$ | $S$ é um multiconjunto de inteiros cuja soma de algum subconjunto é $t$}
- Certificado: Um subconjunto $R \subseteq S$
- Verificador: Soma os elementos de $R$ e verifica se a soma é $t$
- Tempo: $O(n)$ onde $n = |S|$
SAT = {$\langle \phi \rangle$ | $\phi$ é uma fórmula booleana satisfazível}
- Certificado: Uma atribuição de valores para as variáveis
- Verificador: Avalia $\phi$ sob a atribuição
- Tempo: $O(n)$ onde $n$ é o tamanho de $\phi$

Observação Fundamental

Observe que, para todos esses problemas:

Não conhecemos algoritmos polinomiais para resolvê-los (encontrar o certificado)
Mas temos algoritmos polinomiais triviais para verificar uma solução proposta

Esta é a essência da diferença entre P e NP!

A Grande Questão: P vs. NP

É fácil ver que todo problema em P também está em NP. Se podemos resolver um problema em tempo polinomial, podemos certamente verificar uma solução em tempo polinomial (basta ignorar o certificado e resolver o problema do zero). Portanto, $\textbf{P} \subseteq \textbf{NP}$.

A questão de um milhão de dólares, literalmente (oferecido pelo Clay Mathematics Institute), é:

P = NP ?

Se P = NP, isso significaria que todo problema para o qual uma solução pode ser verificada rapidamente também pode ser resolvido rapidamente. Isso teria consequências revolucionárias para a ciência, engenharia, economia e, especialmente, criptografia (que se baseia na dificuldade de certos problemas em NP).
Se P $\neq$ NP, como a maioria dos cientistas da computação acredita, isso significa que existem problemas (como SAT e HAMPATH) que são fundamentalmente mais difíceis de resolver do que de verificar.

Diagrama: A Relação entre P e NP

graph TD
    subgraph "NP (Problemas com verificação rápida)"
        subgraph "P (Problemas com solução rápida)"
            P1["PATH<br/>(caminho em grafo)"]
            P2["RELPRIME<br/>(primalidade relativa)"]
            P3["PRIMES<br/>(teste de primalidade)"]
        end
        NP1["HAMPATH<br/>(caminho hamiltoniano)"]
        NP2["CLIQUE<br/>(k-clique)"]
        NP3["SAT<br/>(satisfatibilidade)"]
        NP4["SUBSET-SUM<br/>(soma de subconjunto)"]
    end

    style P fill:#90EE90
    style NP fill:#FFE4B5

Figura 1: A relação (acreditada) entre as classes P e NP.

Aqui está um diagrama mais completo mostrando também co-NP:

graph TB
    subgraph "Universo de todas as linguagens decidíveis"
        subgraph EXPTIME["EXPTIME (2^n^k^)"]
            subgraph NP_coNP["NP ∪ co-NP"]
                subgraph NP["NP"]
                    NP_only["Problemas em NP?<br/>HAMPATH, SAT, CLIQUE"]
                end
                subgraph coNP["co-NP"]
                    coNP_only["Problemas em co-NP?<br/>UNSAT, TAUTOLOGY"]
                end
                subgraph P_area["P = NP ∩ co-NP"]
                    P["PATH, PRIMES,<br/>RELPRIME"]
                end
            end
            EXP_only["Problemas em EXPTIME<br/>fora de NP/co-NP"]
        end
    end

    style P_area fill:#90EE90
    style NP fill:#FFD700,opacity:0.3
    style coNP fill:#87CEEB,opacity:0.3
    style EXPTIME fill:#FFE4E1,opacity:0.2

Figura 2: Hierarquia das classes de complexidade (conjectural).

Interpretação dos Diagramas

Verde (P): Problemas que sabemos resolver eficientemente
Amarelo (NP): Problemas onde podemos verificar soluções eficientemente
Azul (co-NP): Complementos de problemas em NP
Rosa (EXPTIME): Problemas resolvíveis em tempo exponencial

Questões em aberto:

P = NP? (Acredita-se que não)
NP = co-NP? (Acredita-se que não)
NP ⊊ EXPTIME? (Acredita-se que sim, mas não provado!)

Exemplos em Python: Resolver vs. Verificar

Vamos ilustrar a diferença P vs. NP com problemas concretos, demonstrando a disparidade entre resolver e verificar.

Exemplo 1: SUBSET-SUM

O problema SUBSET-SUM é um exemplo clássico em (Sipser, 2012):

Problema: Dado um conjunto de inteiros $S$ e um alvo $t$, existe um subconjunto de $S$ cuja soma é exatamente $t$?

Comparando um verificador e um resolvedor para SUBSET-SUM

# --- O Verificador (Polinomial) ---
def verificar_subset_sum(conjunto, alvo, certificado):
    """
    Verifica se o 'certificado' (um subconjunto) é uma solução válida.
    Esta operação é RÁPIDA (linear no tamanho do conjunto).
    """
    soma_certificado = sum(certificado)

    # Verifica se a soma está correta e se todos os elementos do certificado
    # realmente pertencem ao conjunto original.
    if soma_certificado != alvo:
        return False

    return all(item in conjunto for item in certificado)

# --- O Resolvedor (Exponencial, força bruta) ---
def resolver_subset_sum_forca_bruta(conjunto, alvo):
    """
    Tenta encontrar uma solução por força bruta.
    Testa TODOS os 2^n subconjuntos possíveis.
    Esta operação é LENTA (exponencial).
    """
    n = len(conjunto)
    # Itera de 1 até 2^n - 1
    for i in range(1, 1 << n):
        soma_atual = 0
        subconjunto_atual = []
        for j in range(n):
            # Usa máscaras de bits para gerar todos os subconjuntos
            if (i >> j) & 1:
                soma_atual += conjunto[j]
                subconjunto_atual.append(conjunto[j])

        if soma_atual == alvo:
            return subconjunto_atual # Encontrou a solução

    return None # Nenhuma solução encontrada

# --- Exemplo de Uso ---
meu_conjunto = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
meu_alvo = 9

print("--- Verificando uma solução (rápido) ---")
solucao_proposta = [3, 1, 5]
resultado_verificacao = verificar_subset_sum(meu_conjunto, meu_alvo, solucao_proposta)
print(f"A solução {solucao_proposta} é válida? {resultado_verificacao}")

print("\n--- Resolvendo do zero (lento) ---")
solucao_encontrada = resolver_subset_sum_forca_bruta(meu_conjunto, meu_alvo)
print(f"Solução encontrada por força bruta: {solucao_encontrada}")

# Demonstrando a diferença de complexidade
print("\n--- Análise de Complexidade ---")
print(f"Tamanho do conjunto: {len(meu_conjunto)}")
print(f"Número de subconjuntos possíveis: 2^{len(meu_conjunto)} = {2**len(meu_conjunto)}")
print(f"Tempo do verificador: O(n) = O({len(meu_conjunto)})")
print(f"Tempo do resolvedor: O(2^n) = O({2**len(meu_conjunto)})")

--- Verificando uma solução (rápido) ---
A solução [3, 1, 5] é válida? True

--- Resolvendo do zero (lento) ---
Solução encontrada por força bruta: [3, 1, 4, 1]

--- Análise de Complexidade ---
Tamanho do conjunto: 11
Número de subconjuntos possíveis: 2^11 = 2048
Tempo do verificador: O(n) = O(11)
Tempo do resolvedor: O(2^n) = O(2048)

Exemplo 2: HAMPATH (Caminho Hamiltoniano)

Vamos implementar verificador e resolvedor para o problema do caminho hamiltoniano:

Verificador e resolvedor para HAMPATH

from itertools import permutations

def verificar_hampath(grafo, inicio, fim, certificado):
    """
    Verifica se 'certificado' é um caminho hamiltoniano válido de inicio até fim.
    Tempo: O(n^2) onde n é o número de vértices.

    Args:
        grafo: dicionário de adjacências {vértice: [vizinhos]}
        inicio: vértice inicial
        fim: vértice final
        certificado: lista de vértices representando o caminho
    """
    # Verifica se começa e termina nos vértices corretos
    if len(certificado) == 0 or certificado[0] != inicio or certificado[-1] != fim:
        return False

    # Verifica se todos os vértices aparecem exatamente uma vez
    if len(certificado) != len(set(certificado)) or len(certificado) != len(grafo):
        return False

    # Verifica se há arestas consecutivas
    for i in range(len(certificado) - 1):
        if certificado[i+1] not in grafo.get(certificado[i], []):
            return False

    return True

def resolver_hampath_forca_bruta(grafo, inicio, fim):
    """
    Encontra um caminho hamiltoniano por força bruta.
    Tempo: O(n!) - MUITO lento!
    """
    vertices = list(grafo.keys())

    # Remove inicio e fim da lista de vértices intermediários
    vertices_meio = [v for v in vertices if v != inicio and v != fim]

    # Testa todas as permutações dos vértices intermediários
    for perm in permutations(vertices_meio):
        caminho = [inicio] + list(perm) + [fim]

        # Verifica se este caminho é válido
        valido = True
        for i in range(len(caminho) - 1):
            if caminho[i+1] not in grafo.get(caminho[i], []):
                valido = False
                break

        if valido:
            return caminho

    return None

# --- Exemplo de Uso ---
# Grafo exemplo: um ciclo com 5 vértices
grafo_exemplo = {
    'A': ['B', 'E'],
    'B': ['A', 'C'],
    'C': ['B', 'D'],
    'D': ['C', 'E'],
    'E': ['D', 'A']
}

print("=== HAMPATH: Caminho Hamiltoniano ===\n")
print(f"Grafo: {grafo_exemplo}\n")

# Testando o verificador
certificado_valido = ['A', 'B', 'C', 'D', 'E']
certificado_invalido = ['A', 'C', 'B', 'D', 'E']

print("--- Verificação (rápida) ---")
print(f"Caminho {certificado_valido}: {verificar_hampath(grafo_exemplo, 'A', 'E', certificado_valido)}")
print(f"Caminho {certificado_invalido}: {verificar_hampath(grafo_exemplo, 'A', 'E', certificado_invalido)}")

print("\n--- Resolução por força bruta (lenta) ---")
solucao = resolver_hampath_forca_bruta(grafo_exemplo, 'A', 'E')
print(f"Caminho encontrado: {solucao}")

print("\n--- Análise de Complexidade ---")
n = len(grafo_exemplo)
print(f"Número de vértices: {n}")
print(f"Permutações a testar: (n-2)! = {n-2}! ≈ {eval(f'__import__(\"math\").factorial({n-2})')}")
print(f"Tempo do verificador: O(n²) = O({n**2})")
print(f"Tempo do resolvedor: O(n!) = crescimento super-exponencial")

=== HAMPATH: Caminho Hamiltoniano ===

Grafo: {'A': ['B', 'E'], 'B': ['A', 'C'], 'C': ['B', 'D'], 'D': ['C', 'E'], 'E': ['D', 'A']}

--- Verificação (rápida) ---
Caminho ['A', 'B', 'C', 'D', 'E']: True
Caminho ['A', 'C', 'B', 'D', 'E']: False

--- Resolução por força bruta (lenta) ---
Caminho encontrado: ['A', 'B', 'C', 'D', 'E']

--- Análise de Complexidade ---
Número de vértices: 5
Permutações a testar: (n-2)! = 3! ≈ 6
Tempo do verificador: O(n²) = O(25)
Tempo do resolvedor: O(n!) = crescimento super-exponencial

Explosão Combinatória

Observe que para HAMPATH com apenas 10 vértices:

O verificador executa em ~100 operações ($10^2$)
O resolvedor força-bruta executa em ~40.320 operações ($8!$)
Com 20 vértices, seria $18! \approx 6.4 \times 10^{15}$ operações!

Esta é a explosão combinatória que torna esses problemas intratáveis na prática.

O código demonstra que a verificação é trivial e rápida, enquanto a resolução por força bruta é muito lenta. A questão P vs. NP, para estes problemas, é: será que existe um algoritmo inteligente que rode em tempo polinomial? (Até hoje, ninguém encontrou um).

Propriedades Importantes da Classe NP

Antes dos exercícios, vejamos algumas propriedades fundamentais de NP conforme (Sipser, 2012):

Teorema: P ⊆ NP

Teorema: $\text{P} \subseteq \text{NP}$

Prova: Seja $L \in \text{P}$. Então existe uma MT determinística $M$ que decide $L$ em tempo polinomial $p(n)$.

Construímos um verificador $V$ para $L$ da seguinte forma:

$V$ recebe entrada $\langle w, c \rangle$ (onde $c$ é um certificado qualquer)
$V$ ignora completamente $c$
$V$ simula $M$ em $w$ e aceita se $M$ aceita

Como $M$ roda em tempo $p(n)$, o verificador $V$ também roda em tempo polinomial. Portanto, $L \in \text{NP}$. $\square$

Fechamento de NP

A classe NP é fechada sob as seguintes operações:

União: Se $L_1, L_2 \in \text{NP}$, então $L_1 \cup L_2 \in \text{NP}$
Concatenação: Se $L_1, L_2 \in \text{NP}$, então $L_1 \circ L_2 \in \text{NP}$
Estrela de Kleene: Se $L \in \text{NP}$, então $L^* \in \text{NP}$

Ideia: Os certificados podem ser combinados de forma apropriada. Por exemplo, para união, o certificado indica qual linguagem aceita a entrada e fornece o certificado correspondente.

Co-NP

Define-se também a classe co-NP:

\[ \text{co-NP} = \{ L \mid \overline{L} \in \text{NP} \} \]

Ou seja, co-NP contém os complementos das linguagens em NP.

Exemplo: $\overline{\text{SAT}}$ = “esta fórmula é insatisfazível?” está em co-NP.

Questão aberta: NP = co-NP? (Acredita-se que não)

Observação: Se P = NP, então NP = co-NP (pois P é fechado sob complemento).

Exercícios de Verificação

Atividade Prática

Classificação: O problema do Caixeiro Viajante (TSP) pergunta: “Dado um conjunto de cidades e distâncias entre elas, existe um tour que visita todas as cidades e retorna à origem com um custo total menor que $k$?”. Explique por que este problema está na classe NP. Qual seria o certificado?
P ou NP?: Considere o problema de Multiplicação de Matrizes: “Dadas duas matrizes $A$ e $B$, o produto delas é $C$?”. Este problema está em P ou apenas em NP? Justifique.
Implicações: Suponha que um pesquisador anuncie amanhã que provou que P = NP. Qual seria a implicação mais significativa para a segurança na internet, que depende de algoritmos como o RSA (cuja segurança se baseia na dificuldade de fatorar grandes números)?
Verificadores: Considere o problema COMPOSTOS = {$\langle n \rangle$ | $n$ é um número composto (não-primo)}. Mostre que este problema está em NP construindo um verificador apropriado. Qual seria o certificado?
Co-NP: O problema $\overline{\text{HAMPATH}}$ = “o grafo $G$ NÃO possui caminho hamiltoniano de $s$ para $t$” está em co-NP. Por que é difícil mostrar que está em NP? O que seria um certificado para provar que não existe caminho hamiltoniano?
Fechamento: Use a propriedade de fechamento sob união para mostrar que o problema “existe um caminho hamiltoniano OU uma 3-clique em $G$?” está em NP.

Gabarito Resumido

TSP em NP: O problema está em NP porque, embora encontrar o tour ótimo seja difícil, verificar um tour proposto é fácil.
- Certificado: Uma sequência de cidades que representa um tour (ex: “Cidade A -> Cidade C -> Cidade B -> … -> Cidade A”).
- Verificador: Um algoritmo que recebe o certificado e:
  1. Verifica se a sequência contém todas as cidades exatamente uma vez (exceto pelo início/fim).
  2. Soma as distâncias do tour proposto.
  3. Compara a soma com o limite $k$. Todas essas etapas são rápidas e podem ser feitas em tempo polinomial.
Multiplicação de Matrizes: Este problema está na classe P. Podemos tanto resolver quanto verificar em tempo polinomial. O algoritmo padrão para multiplicar duas matrizes $n \times n$ tem complexidade $O(n^3)$ (e existem algoritmos mais rápidos, como o de Strassen). Como existe um algoritmo de resolução em tempo polinomial, o problema está em P. Lembre-se que se um problema está em P, ele também está em NP.
Implicações de P = NP: Se P = NP, isso significaria que problemas considerados difíceis (como a fatoração de grandes números, que está em NP) poderiam ser resolvidos eficientemente. A segurança do RSA se baseia na premissa de que fatorar o produto de dois grandes números primos é computacionalmente inviável (intratável). Se P = NP, provavelmente existiria um algoritmo de tempo polinomial para fatoração, o que permitiria quebrar a criptografia RSA rapidamente. Isso tornaria a maior parte da segurança da internet (HTTPS, transações bancárias, etc.) obsoleta da noite para o dia.
COMPOSTOS em NP:
- Certificado: Um divisor $d$ de $n$ tal que $1 < d < n$
- Verificador:
```
V(n, d):
  1. Verifica se 1 < d < n
  2. Verifica se d divide n (calcula n mod d)
  3. Aceita se d | n
```
- Tempo: $O(\log^2 n)$ (para a divisão), que é polinomial no tamanho da entrada $\log n$ bits.
- Observação: COMPOSTOS também está em P (pelo teste AKS), e seu complemento PRIMES está em P.
$\overline{\text{HAMPATH}}$ e Co-NP:
- É difícil mostrar que está em NP porque não sabemos que tipo de certificado “curto” (polinomial) poderia provar que NÃO existe um caminho hamiltoniano
- Um certificado ingênuo seria listar TODOS os possíveis caminhos e mostrar que nenhum é hamiltoniano, mas isso teria tamanho exponencial ($n!$ possibilidades)
- Esta assimetria entre provas de existência (fáceis de certificar) e provas de inexistência (aparentemente difíceis de certificar) é fundamental na teoria da complexidade
- Se conseguíssemos mostrar que $\overline{\text{HAMPATH}} \in \text{NP}$, teríamos que NP = co-NP, o que resolveria parcialmente a questão P vs NP!
Fechamento sob União:
- Sejam $L_1 = \text{HAMPATH}$ e $L_2 = \text{3-CLIQUE}$
- Sabemos que $L_1, L_2 \in \text{NP}$ com verificadores $V_1$ e $V_2$
- Para $L = L_1 \cup L_2$, construímos o verificador:
```
V(G, c):
  1. Interpreta c = (b, c') onde b ∈ {0,1} e c' é um certificado
  2. Se b = 0: executa V₁(G, c') e retorna seu resultado
  3. Se b = 1: executa V₂(G, c') e retorna seu resultado
```
- O certificado $c$ indica qual linguagem aceita $G$ e fornece o certificado correspondente
- Como $V_1$ e $V_2$ rodam em tempo polinomial, $V$ também roda em tempo polinomial
- Portanto, $L_1 \cup L_2 \in \text{NP}$

Perspectivas e Importância Histórica

A questão P vs. NP é considerada por muitos como o problema mais importante da ciência da computação, e um dos problemas mais importantes de toda a matemática.

O Prêmio do Milênio

Em 2000, o Clay Mathematics Institute designou P vs. NP como um dos sete Problemas do Prêmio do Milênio, oferecendo US$ 1.000.000 pela primeira solução correta.

Até hoje, o problema permanece sem solução. Apenas um dos sete problemas (a Conjectura de Poincaré) foi resolvido desde então.

Por que P vs. NP é tão importante?

Implicações práticas: Milhares de problemas importantes em otimização, planejamento, design de circuitos, bioinformática, etc., são NP-completos (próxima aula). Se P = NP, todos eles teriam soluções eficientes.
Fundamentos da criptografia: A segurança de praticamente toda a criptografia moderna depende da suposição de que P ≠ NP.
Limites da computação: A resposta determinará limites fundamentais sobre o que computadores podem fazer eficientemente.
Filosofia da matemática: Relaciona-se com questões profundas sobre provas matemáticas. Se P = NP, existiriam “atalhos” para encontrar provas de teoremas (Sipser, 2012).

Evidências e Crenças

Por que a maioria dos cientistas acredita que P ≠ NP?

Décadas de tentativas: Milhares de pesquisadores tentaram encontrar algoritmos polinomiais para problemas NP-completos por mais de 50 anos, sem sucesso.
Separações em outros modelos: Existem separações análogas em outros modelos de computação.
Intuição: Parece “improvável” que verificar seja tão fácil quanto encontrar.

Mas não temos prova! Todas as tentativas de provar P ≠ NP esbarraram em barreiras técnicas fundamentais, como:

Barreiras de relativização
Barreiras de algebrização
Barreiras de circuitos booleanos

Curiosidade Histórica

O problema P vs. NP foi formalmente formulado por Stephen Cook em 1971 e, independentemente, por Leonid Levin na URSS. Suas contribuições fundamentais levaram à descoberta dos problemas NP-completos (que estudaremos na próxima aula).

A carta de Kurt Gödel para John von Neumann em 1956 já discutia essencialmente a mesma questão, mostrando que a ideia é ainda mais antiga! (Sipser, 2012)

Próximos Passos

Na próxima aula, estudaremos os problemas NP-completos: problemas em NP que são, em certo sentido, os “mais difíceis” de NP. Veremos que:

Se algum problema NP-completo estiver em P, então P = NP
Se algum problema NP-completo não estiver em P, então P ≠ NP

Isso torna os problemas NP-completos centrais para resolver a questão P vs. NP!

Referências Bibliográficas

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