Redução (complexidade)

Em teoria da computação e complexidade, uma redução é uma transformação de um problema em outro. Dependendo da transformação utilizada, isto pode ser usado para definir classes de complexidade em um conjunto de problemas. Intuitivamente, o problema A é redutível ao problema B se existe uma maneira de transformar uma solução para B numa solução para A sempre que A tem solução. Assim, solucionar A não pode ser mais difícil que solucionar B. Escrevemos A ≤_mB, geralmente com um símbolo subscrito no ≤ para indicar o tipo de redução que foi usada (m: redução por mapeamento; P: redução polinomial).

Introdução

São duas as principais razões para se realizar reduções:

• Primeira: Frequentemente nos deparamos tentando resolver um problema que é parecido com um problema que já resolvemos. Nestes casos, muitas vezes uma maneira mais rápida de resolver o novo problema é transformar cada instância do novo problema em uma instância do problema antigo, resolvê-la usando nossa solução existente, e então usar esta para obter nossa solução final. Este é, talvez, o uso mais óbvio de reduções.
• Segunda: Outro uso, mais sutil é o seguinte. Suponha que tenhamos um problema que provamos que é difícil de resolver, e temos um novo problema parecido. Podemos suspeitar que este, também é difícil de resolver. Argumentamos por contradição: suponha que o novo problema é fácil de resolver. Então, se podemos mostrar que cada instância do problema antigo pode ser resolvida facilmente transformando-a em uma instância do novo problema, temos uma contradição, o que estabelece que o novo problema também é difícil.

Um exemplo muito simples é a redução de multiplicação para elevação ao quadrado. Suponha que tudo que sabemos fazer é somar, subtrair, elevar ao quadrado e dividir por dois. Podemos usar este conhecimento, combinado com a fórmula a seguir, para obter o produto de quaisquer dois números:

$a\times b={\frac {\left(\left(a+b\right)^{2}-a^{2}-b^{2}\right)}{2}}$

Também temos uma redução na outra direção, obviamente, se podemos multiplicar dois números, podemos elevá-los ao quadrado. Isto parece implicar que estes problemas são igualmente difíceis. Este tipo de redução corresponde à Redutibilidade de Turing.

No entanto, a redução se torna mais difícil se adicionarmos a restrição de que só podemos usar a função quadrática uma vez e somente no final. Neste caso, mesmo se nos fosse permitido usar todas as operações aritméticas básicas, incluindo multiplicação, não existiria redução em geral, pois não se pode computar um número irracional como ${\sqrt {2}}$ de números racionais. Indo para a outra direção, no entanto, podemos certamente elevar ao quadrado um número só com uma multiplicação, no final. Usando esta forma limitada de redução, mostramos um resultado não surpreendente, que multiplicação é mais difícil, em geral, que elevar ao quadrado. Este tipo de redução corresponde à redução por mapeamento.

Definição

Dados dois subconjuntos A e B de N e um conjunto de funções F de N para N que é fechada sob função composta, A é chamado redutível a B sob F se

$\exists f\in F{\mbox{ . }}\forall x\in \mathbb {N} {\mbox{ . }}x\in A\Leftrightarrow f(x)\in B$

Escrevemos

$A\leq _{F}B$

Seja S um subconjunto de P(N) e ≤ uma redução, então S é chamado fechado sob ≤ se

$\forall s\in S{\mbox{ . }}\forall A\in P(\mathbb {N} ){\mbox{ . }}A\leq s\Rightarrow A\in S$

Um subconjunto A de N é chamado difícil para S se

$\forall s\in S{\mbox{ . }}s\leq A$

Um subconjunto A de N é chamado completo para S se A é difícil para S e A está em S.

Propriedades

Uma redução quasi ordem, é reflexiva e transitiva, em P(N)×P(N), onde P(N) é o conjunto das partes dos números naturais.

Tipos e aplicações de redução

Como descrito no exemplo acima, existem dois tipos de redução usados em complexidade computacional, redução por mapeamento e Turing-redução. Redução por mapeamento, mapeia instâncias de um problema em instâncias de outro; Turing-reduções computam a solução de um problema, assumindo que o outro problema é fácil de resolver. Uma redução por mapeamento é mais fraca que uma Turing-redução. Reduções fracas são mais efetivas na hora de separar problemas, mas elas têm menos poder, fazendo com que as reduções sejam mais difíceis de determinar.

Um problema é completo para uma classe de complexidade se todo problema nesta classe se reduz a este problema, e ele mesmo está na classe também. Neste caso o problema representa a classe, uma vez que qualquer solução para ele, em combinação com reduções, é usada para resolver todo problema na classe.

No entanto, por questão de utilidade, reduções devem ser fáceis. Por exemplo, é quase impossível reduzir um problema difícil-de-resolver NP-completo como SAT para um problema trivial, como determinar se um número é igual a zero, fazendo com que a máquina de redução resolva o problema em tempo exponencial e dê zero como saída só se existe uma solução. No entanto, isto não significa muito, porque mesmo que possamos resolver o novo problema, reduzi-lo é tão difícil quanto resolver o problema antigo. Da mesma forma, reduzir computacionalmente uma função incomputável pode reduzir um problema indecidível para um decidível. Como Michael Sipser salienta em Introduction to the Theory of Computation: "Uma redução deve ser fácil, relativa à complexidade de problemas típicos da classe [...] Se a redução era difícil de computar, uma solução fácil para o problema completo não necessariamente produziria uma solução fácil para os problemas reduzidos a ele."

Portanto, a noção apropriada de redução depende da classe de complexidade sendo estudada. Ao estudar a classe de complexidade NP e classes mais difíceis como hierarquia polinomial, reduções em tempo polinomial são usadas. Ao estudar classes dentro de P como NC e NL, reduções log-space são usadas. Reduções também são usadas em teoria da computabilidade para mostrar se os problemas são ou não são solucionáveis por máquinas em geral; neste caso, reduções são restritas a funções computáveis.

No caso de problemas de otimização (maximização ou minimização), frequentemente pensamos em termos de reduções aproximadas. Suponha que tenhamos dois problemas de otimização de modo que as instâncias de um problema podem ser mapeadas em instâncias do outro, de forma que as soluções quase ótimas do último podem ser transformadas em soluções quase ótimas para o primeiro. Desta forma, se temos um algoritmo de otimização (ou algoritmo de aproximação) que acha soluções quase ótimas (ou ótimas) para instâncias do problema B, e uma redução eficiente aproximada de um problema A para um problema B, por composição obtemos um algoritmo de otimização que produz soluções quase ótimas para instâncias do problema A. Reduções de aproximação são geralmente usadas para provar a dificuldade dos resultados de aproximação: se algum problema de otimização A é difícil de aproximar (sob alguma hipótese de complexidade) em um fator melhor que α para algum α, se existe uma β-redução por aproximação do problema A para o problema B, podemos concluir que o problema B é difícil de aproximar no fator α/β.

Exemplos

• Para mostrar que um problema de decisão P é indecidível devemos achar uma redução de um problema de decisão que já é reconhecidamente indecidível para P. A função de redução deve ser uma redução computável. Em particular, geralmente mostramos que um problema P é indecidível mostrando que o problema da parada reduz a P.
• As classes de complexidade P, NP e PSPACE são fechados sob reduções em tempo polinomial.
• As classes de complexidade L, NL, P, NP e PSPACE são fechadas sob redução log-space.

Exemplo detalhado

O exemplo a seguir mostra como usar redução do problema da parada para provar que uma linguagem é indecidível. Suponha H(M, w) é um problema de determinar se uma dada máquina de Turing M para (aceitando ou rejeitando) sobre uma cadeia de entrada w. Esta linguagem é conhecida por ser indecidível. Suponha E(M) é o problema de determinar se a linguagem de uma dada máquina de Turing M aceita está vazia (em outras palavras, se M não aceita nenhuma cadeia). Mostramos que E é indecidível por redução de H.

Para obter uma contradição, suponha que R é um decisor para E. Vamos usar isto para produzir um decisor S para H (que sabemos que não existe). Dada uma entrada M e w (uma máquina de Turing e uma cadeia de entrada), defina S(M, w) com o seguinte comportamento: S cria uma máquina de Turing N que aceita só se a entrada para N é w e M para sobre a entrada w, e não para em outra maneira. O decisor S pode agora avaliar R(N) para checar se a linguagem aceita por N é vazia. Se R aceita N, então a linguagem aceita por N é vazia, então em particular M não para sobre a entrada w, então S pode rejeitar. Se R rejeita N, então a linguagem aceita por N não é vazia, então M não para sobre a entrada w, então S pode aceitar. Assim, se temos um decisor R para E, podemos produzir um decisor S para o problema da parada H(M, w) para qualquer maquina M e entrada w. Como sabemos que S não existe, a linguagem E também é indecidível.

Referências

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, MIT Press, 2001, ISBN 978-0-262-03293-3
• Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967, ISBN 978-0-262-68052-3.
• Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory, Springer, 2000, ISBN 978-3-540-66752-0.
• E.R. Griffor: Handbook of Computability Theory, North Holland, 1999, ISBN 978-0-444-89882-1.