Redutibilidade e Completude

Computabilidade e Complexidade

Autor

Márcio Nicolau

Data de Publicação

20 de outubro de 2025

Objetivos da Aula

  • Definir formalmente o conceito de redutibilidade entre problemas.
  • Aplicar a redutibilidade como a principal ferramenta para provar a indecidibilidade de novos problemas.
  • Entender o que significa um problema ser “completo” para uma classe de linguagens.
  • Identificar \(A_{TM}\) como o problema canônico RE-Completo.

Conteúdo

O Conceito de Redutibilidade

Nós provamos que o problema da aceitação, \(A_{TM}\), é indecidível usando uma complexa prova por diagonalização. Agora, para cada novo problema que suspeitamos ser indecidível, teremos que criar uma nova prova por diagonalização do zero? Felizmente, não.

A redutibilidade é uma técnica que nos permite usar um problema que já sabemos ser difícil (como \(A_{TM}\)) para provar que um novo problema também é difícil.

NotaA Intuição da Redução

Reduzir um problema A a um problema B significa mostrar que, se tivéssemos uma “caixa mágica” que resolve B, poderíamos usá-la para resolver A. Isso implica que B é pelo menos tão difícil quanto A. Se A é indecidível, B não pode ser decidível.

Definição Formal (Redutibilidade por Mapeamento):

Uma linguagem \(A\) é redutível por mapeamento (ou many-one redutível) à linguagem \(B\), denotado \(A \leq_m B\), se existe uma função computável \(f\) 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\] A função \(f\) é chamada de redução de \(A\) para \(B\). (Sipser, 2012, p. 235)

Diagrama: Como Funciona uma Redução

graph TD
    subgraph "Universo do Problema A"
        A_yes["w ∈ A"]
        A_no["w' ∉ A"]
    end
    
    subgraph "Universo do Problema B"
        B_yes["f(w) ∈ B"]
        B_no["f(w') ∉ B"]
    end

    A_yes -- "f(w)" --> B_yes
    A_no -- "f(w')" --> B_no

    style A_yes fill:#e8f5e9
    style B_yes fill:#e8f5e9
    style A_no fill:#ffcdd2
    style B_no fill:#ffcdd2
Figura 1: A função computável ‘f’ atua como uma ponte entre o problema A e o problema B.

Usando Reduções para Provar Indecidibilidade

A principal aplicação da redutibilidade na teoria da computabilidade é o seguinte teorema:

ImportanteTeorema da Redução para Indecidibilidade

Se \(A \leq_m B\) e a linguagem \(A\) é indecidível, então a linguagem \(B\) também deve ser indecidível.

Prova (por contradição):

Suponha que \(B\) fosse decidível por uma TM \(M_B\). Poderíamos então construir um decisor para \(A\) da seguinte forma: 1. Dada uma entrada \(w\) para o problema \(A\). 2. Use a função computável \(f\) para transformar \(w\) em \(f(w)\). 3. Execute o decisor \(M_B\) na entrada \(f(w)\). 4. Se \(M_B\) aceita, aceite \(w\). Se \(M_B\) rejeita, rejeite \(w\).

Este procedimento seria um decisor para \(A\). Mas nós sabemos que \(A\) é indecidível. Chegamos a uma contradição. Portanto, nossa suposição de que \(B\) era decidível deve ser falsa.

Exemplo de Prova por Redução: \(A_{TM} \leq_m HALT_{TM}\)

Vamos provar que \(HALT_{TM} = \{\langle M, w \rangle \mid M \text{ para em } w\}\) é indecidível, usando \(A_{TM}\) como nosso ponto de partida.

Construção da Redução (\(f\)):

A redução \(f\) recebe uma entrada \(\langle M, w \rangle\) para o problema \(A_{TM}\) e deve produzir uma saída \(\langle M', w' \rangle\) para o problema \(HALT_{TM}\).

Definimos \(f(\langle M, w \rangle) = \langle M', w \rangle\), onde \(M'\) é uma nova TM que se comporta da seguinte maneira:

M'(x):
1. Execute M na entrada w (ignorando a entrada original x).
2. Se M aceitar w, então M' aceita x (e para).
3. Se M rejeitar w, então M' entra em um loop infinito.

Análise da Redução:

  • Se \(\langle M, w \rangle \in A_{TM}\) (ou seja, \(M\) aceita \(w\)), então a máquina \(M'\) irá parar na sua etapa 2 para qualquer entrada. Portanto, \(\langle M', w \rangle \in HALT_{TM}\).
  • Se \(\langle M, w \rangle \notin A_{TM}\) (ou seja, \(M\) rejeita ou entra em loop em \(w\)), então a máquina \(M'\) ou entrará em loop na sua etapa 1 (se M entrar em loop) ou na sua etapa 3 (se M rejeitar). Em ambos os casos, \(M'\) não para. Portanto, \(\langle M', w \rangle \notin HALT_{TM}\).

A equivalência \(\langle M, w \rangle \in A_{TM} \iff \langle M', w \rangle \in HALT_{TM}\) é mantida. Como \(A_{TM}\) é indecidível, concluímos que \(HALT_{TM}\) também é indecidível.

Problemas Completos: Os “Mais Difíceis”

Dentro de uma classe de complexidade (como RE), alguns problemas se destacam por serem os “mais difíceis” do grupo. Um problema é “o mais difícil” se qualquer outro problema daquela classe pode ser reduzido a ele.

NotaDefinição: Completude

Um problema \(B\) é completo para uma classe de linguagens \(\mathcal{C}\) (ou \(\mathcal{C}\)-completo) se ele satisfaz duas condições:

  1. \(B\) está em \(\mathcal{C}\) (\(B \in \mathcal{C}\)).
  2. Todo problema \(A\) em \(\mathcal{C}\) é redutível a \(B\) (\(\forall A \in \mathcal{C}, A \leq_m B\)).

\(A_{TM}\) é RE-Completo

O problema da aceitação, \(A_{TM}\), é o exemplo canônico de um problema RE-Completo. (Sipser, 2012)

  1. \(A_{TM} \in \text{RE}\): Nós já estabelecemos que \(A_{TM}\) é reconhecível por uma Máquina de Turing Universal que simula a máquina de entrada.

  2. Todo problema em RE é redutível a \(A_{TM}\): Seja \(L\) uma linguagem qualquer em RE. Por definição, existe uma TM, \(M_L\), que a reconhece. A redução \(f\) de \(L\) para \(A_{TM}\) é trivial: \(f(w) = \langle M_L, w \rangle\).

    • Se \(w \in L\), então \(M_L\) aceita \(w\), e, por definição, \(f(w) = \langle M_L, w \rangle \in A_{TM}\).
    • Se \(w \notin L\), então \(M_L\) não aceita \(w\), e, por definição, \(f(w) = \langle M_L, w \rangle \notin A_{TM}\). A redução funciona.

Diagrama: O Status de \(A_{TM}\) como RE-Completo

graph TD
    subgraph "Classe RE"
        A["Outro problema L₁ ∈ RE"]
        B["Outro problema L₂ ∈ RE"]
        C["..."]
        
        ATM["<b>A_TM</b> (RE-Completo)"]
    end

    A -->|≤ₘ| ATM
    B -->|≤ₘ| ATM
    C -->|≤ₘ| ATM
    
    style ATM fill:#ff9999,stroke:#b71c1c,stroke-width:2px
Figura 2: A_TM é o “cume da montanha” da classe RE. Todos os outros problemas em RE podem ser “escalados” até ele através de uma redução.

Aplicação em Código: A Ideia da Redução

A construção de uma redução é como escrever um “wrapper” ou uma “função de pré-processamento”. O código Python abaixo não implementa uma redução de TM (que seria muito complexo), mas ilustra a lógica de transformar a instância de um problema em outro.

Ilustração da lógica de redução em Python 
# Suponha que temos uma "caixa mágica" que resolve um problema B
def magic_solver_for_B(instancia_b):
    """Esta é a nossa hipotética caixa mágica (oráculo) para o problema B.
    Ex: B = Problema da Parada"""
    print(f"  [Oráculo B] Recebeu a instância: {instancia_b}")
    # A lógica interna é desconhecida, mas sabemos que funciona.
    # Para este exemplo, vamos supor que ele resolve HALT_TM.
    # Instância é um tuple (maquina_str, entrada_str)
    maquina, entrada = instancia_b
    if "loop" in maquina:
        print("  [Oráculo B] Concluiu: NÃO PARA.")
        return False
    else:
        print("  [Oráculo B] Concluiu: PARA.")
        return True

# Queremos resolver o problema A, que sabemos ser difícil
# A = Problema da Aceitação (A_TM)

def reduction_A_to_B(instancia_a):
    """Esta é a nossa função de redução 'f'.
    Transforma uma instância de A_TM em uma de HALT_TM."""
    print(f"[Redução] Recebeu instância de A: {instancia_a}")
    maquina_M, entrada_w = instancia_a
    
    # Construímos a descrição da nova máquina M'
    maquina_M_prime = f"""
    def M_prime(x):
        # Simula M em w
        resultado_M_em_w = simular("{maquina_M}", "{entrada_w}")
        if resultado_M_em_w == "aceita":
            return "para"
        else: # rejeita ou loop
            return "loop infinito" # Forçamos o loop
    """
    
    instancia_b = (maquina_M_prime, entrada_w)
    print(f"[Redução] Produziu instância de B: {instancia_b}")
    return instancia_b

def solver_for_A(instancia_a):
    """Este é o nosso decisor para A, construído usando a redução e o oráculo para B."""
    print(f"\nTentando resolver o problema A para a instância: {instancia_a}...")
    
    # 1. Reduzir a instância de A para uma instância de B
    instancia_b = reduction_A_to_B(instancia_a)
    
    # 2. Usar o oráculo de B para resolver a instância transformada
    resultado_b = magic_solver_for_B(instancia_b)
    
    print(f"Resultado final para A: {'ACEITA' if resultado_b else 'NÃO ACEITA'}")
    return resultado_b

# --- Exemplo de Uso ---
# Instância de A_TM: M aceita w?
instancia_problema_A = ("def M(w): return 'aceita'", "input_string")
solver_for_A(instancia_problema_A)

# Instância de A_TM: M rejeita w? (o que M' transformará em loop)
instancia_problema_A_2 = ("def M(w): return 'rejeita'", "input_string")
solver_for_A(instancia_problema_A_2)

Tentando resolver o problema A para a instância: ("def M(w): return 'aceita'", 'input_string')...
[Redução] Recebeu instância de A: ("def M(w): return 'aceita'", 'input_string')
[Redução] Produziu instância de B: ('\n    def M_prime(x):\n        # Simula M em w\n        resultado_M_em_w = simular("def M(w): return \'aceita\'", "input_string")\n        if resultado_M_em_w == "aceita":\n            return "para"\n        else: # rejeita ou loop\n            return "loop infinito" # Forçamos o loop\n    ', 'input_string')
  [Oráculo B] Recebeu a instância: ('\n    def M_prime(x):\n        # Simula M em w\n        resultado_M_em_w = simular("def M(w): return \'aceita\'", "input_string")\n        if resultado_M_em_w == "aceita":\n            return "para"\n        else: # rejeita ou loop\n            return "loop infinito" # Forçamos o loop\n    ', 'input_string')
  [Oráculo B] Concluiu: NÃO PARA.
Resultado final para A: NÃO ACEITA

Tentando resolver o problema A para a instância: ("def M(w): return 'rejeita'", 'input_string')...
[Redução] Recebeu instância de A: ("def M(w): return 'rejeita'", 'input_string')
[Redução] Produziu instância de B: ('\n    def M_prime(x):\n        # Simula M em w\n        resultado_M_em_w = simular("def M(w): return \'rejeita\'", "input_string")\n        if resultado_M_em_w == "aceita":\n            return "para"\n        else: # rejeita ou loop\n            return "loop infinito" # Forçamos o loop\n    ', 'input_string')
  [Oráculo B] Recebeu a instância: ('\n    def M_prime(x):\n        # Simula M em w\n        resultado_M_em_w = simular("def M(w): return \'rejeita\'", "input_string")\n        if resultado_M_em_w == "aceita":\n            return "para"\n        else: # rejeita ou loop\n            return "loop infinito" # Forçamos o loop\n    ', 'input_string')
  [Oráculo B] Concluiu: NÃO PARA.
Resultado final para A: NÃO ACEITA
False

Exercícios de Verificação

NotaAtividade Prática

  1. Conceitual: Se você prova que \(A \leq_m B\) e você sabe que a linguagem \(B\) é decidível, o que você pode concluir sobre a linguagem \(A\)? Por quê?

  2. Redução: Considere a linguagem \(ALL_{TM} = \{\langle M \rangle \mid L(M) = \Sigma^*\}\), ou seja, o conjunto de TMs que aceitam todas as strings. Prove que \(ALL_{TM}\) é indecidível por meio de uma redução a partir de \(A_{TM}\).

  3. Completude: O problema \(HALT_{TM}\) também é RE-completo. Para provar isso, quais duas condições você precisaria verificar?

  1. Conclusão: Se \(A \leq_m B\) e \(B\) é decidível, então \(A\) também é decidível. A justificativa é o próprio mecanismo da redução: podemos construir um decisor para \(A\) que primeiro usa a função computável \(f\) para converter a entrada de \(A\) para uma entrada de \(B\), e depois usa o decisor de \(B\) para obter a resposta. Como ambas as etapas (cálculo de \(f\) e decisão de \(B\)) param, o processo todo para.

  2. Redução para \(ALL_{TM}\): Reduzimos \(A_{TM}\) para \(ALL_{TM}\).

    • Função de Redução (\(f\)): Dado \(\langle M, w \rangle\), a função \(f\) constrói uma nova TM, \(M_w\).

    • Construção de \(M_w\): A máquina \(M_w\) recebe uma entrada \(x\) e faz o seguinte: ignora \(x\) completamente e simula \(M\) na entrada original \(w\). Se \(M\) aceita \(w\), então \(M_w\) aceita \(x\). Caso contrário, \(M_w\) rejeita \(x\).

    • Análise:

      • Se \(\langle M, w \rangle \in A_{TM}\) (M aceita w), então \(M_w\) aceitará qualquer entrada \(x\). Logo, \(L(M_w) = \Sigma^*\), e \(\langle M_w \rangle \in ALL_{TM}\).
      • Se \(\langle M, w \rangle \notin A_{TM}\) (M não aceita w), então \(M_w\) nunca aceitará sua entrada. Logo, \(L(M_w) = \emptyset\), e \(\langle M_w \rangle \notin ALL_{TM}\).

    • A equivalência é mantida. Como \(A_{TM}\) é indecidível, \(ALL_{TM}\) também é.

  3. Condições para \(HALT_{TM}\) ser RE-Completo:

    1. \(HALT_{TM} \in \text{RE}\): Precisamos mostrar que o problema é Turing-reconhecível. (Isto é verdade: um reconhecedor pode simplesmente simular \(M\) em \(w\). Se a simulação parar, ele aceita. Se não, ele entra em loop, o que é permitido para um reconhecedor).
    2. Todo problema em RE é redutível a \(HALT_{TM}\): Precisamos mostrar que para toda linguagem \(L \in \text{RE}\), existe uma redução \(L \leq_m HALT_{TM}\). (Isto também é verdade e pode ser provado mostrando que \(A_{TM} \leq_m HALT_{TM}\), e como todo \(L \in RE\) se reduz a \(A_{TM}\), por transitividade, todo \(L\) se reduz a \(HALT_{TM}\)).

Referências Bibliográficas

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