Redução (complexidade) - Reduction (complexity)

Exemplo de uma redução do problema de satisfatibilidade booleana ( AB ) ∧ (¬ A ∨ ¬ B ∨ ¬ C ) ∧ (¬ ABC ) para um problema de cobertura de vértices . Os vértices azuis formam uma cobertura mínima de vértices e os vértices azuis no oval cinza correspondem a uma atribuição de verdade satisfatória para a fórmula original.

Na teoria da computabilidade e na teoria da complexidade computacional , uma redução é um algoritmo para transformar um problema em outro problema. Uma redução suficientemente eficiente de um problema para outro pode ser usada para mostrar que o segundo problema é pelo menos tão difícil quanto o primeiro.

Intuitivamente, o problema A é redutível ao problema B , se um algoritmo para resolver o problema B com eficiência (se existisse) também pudesse ser usado como uma sub-rotina para resolver o problema A com eficiência. Quando isso for verdade, resolver A não pode ser mais difícil do que resolver B . "Mais difícil" significa ter uma estimativa mais alta dos recursos computacionais necessários em um determinado contexto (por exemplo, maior complexidade de tempo , maior requisito de memória, necessidade cara de núcleos de processador de hardware extras para uma solução paralela em comparação com uma solução de thread único, etc.) . A existência de uma redução de A para B pode ser escrita na notação abreviada Am B , geralmente com um subscrito em ≤ para indicar o tipo de redução que está sendo usado (m: redução de mapeamento , p: redução polinomial ).

A estrutura matemática gerada em um conjunto de problemas pelas reduções de um determinado tipo geralmente forma uma pré - ordem , cujas classes de equivalência podem ser utilizadas para definir graus de insolvência e classes de complexidade .

Introdução

Existem duas situações principais em que precisamos usar reduções:

  • Primeiro, nos encontramos tentando resolver um problema que é semelhante a um problema que já resolvemos. Nesses casos, geralmente uma maneira rápida de resolver o novo problema é transformar cada instância do novo problema em instâncias do problema antigo, resolvê-los usando nossa solução existente e, em seguida, usá-los para obter nossa solução final. Este é talvez o uso mais óbvio de reduções.
  • Segundo: suponha que temos um problema que provamos ser difícil de resolver e temos um novo problema semelhante. Podemos suspeitar que também seja difícil de resolver. Argumentamos por contradição: suponha que o novo problema seja fácil de resolver. Então, se pudermos mostrar que cada instância do antigo problema pode ser resolvida facilmente, transformando-a em instâncias do novo problema e resolvendo-as, teremos uma contradição. Isso estabelece que o novo problema também é difícil.

Um exemplo muito simples de redução é da multiplicação para o quadrado . Suponha que tudo o que sabemos fazer seja somar, subtrair, tirar quadrados e dividir por dois. Podemos usar esse conhecimento, combinado com a seguinte fórmula, para obter o produto de quaisquer dois números:

Também temos uma redução na outra direção; obviamente, se podemos multiplicar dois números, podemos elevar ao quadrado um número. Isso parece implicar que esses dois problemas são igualmente difíceis. Este tipo de redução corresponde à redução de Turing .

No entanto, a redução se torna muito mais difícil se adicionarmos a restrição de que só podemos usar a função de quadratura uma vez e apenas no final. Neste caso, mesmo que possamos usar todas as operações aritméticas básicas, incluindo a multiplicação, não existe redução em geral, porque para obter o resultado desejado como um quadrado temos que calcular primeiro sua raiz quadrada, e este quadrado root pode ser um número irracional como aquele que não pode ser construído por operações aritméticas em números racionais. Indo na outra direção, entretanto, certamente podemos elevar ao quadrado um número com apenas uma multiplicação, apenas no final. Usando essa forma limitada de redução, mostramos o resultado não surpreendente de que a multiplicação é geralmente mais difícil do que o quadrado. Isso corresponde à redução muitos-um .

Propriedades

Uma redução é uma pré - ordenação , que é uma relação reflexiva e transitiva , em P ( N ) × P ( N ), onde P ( N ) é o conjunto de potências dos números naturais .

Tipos e aplicações de reduções

Conforme descrito no exemplo acima, existem dois tipos principais de reduções usadas na complexidade computacional, a redução muitos-um e a redução de Turing . As reduções muitos-um mapeiam as instâncias de um problema para as instâncias de outro; As reduções de Turing calculam a solução para um problema, assumindo que o outro problema seja fácil de resolver. A redução muitos-um é um tipo mais forte de redução de Turing e é mais eficaz na separação de problemas em classes de complexidade distintas. No entanto, o aumento das restrições às reduções muitos-um torna mais difícil encontrá-las.

Um problema está completo para uma classe de complexidade se todos os problemas da classe se reduzirem a esse problema e também estiver na própria classe. Nesse sentido, o problema representa a classe, uma vez que qualquer solução para ele pode, em combinação com as reduções, ser utilizada para resolver todos os problemas da classe.

No entanto, para serem úteis, as reduções devem ser fáceis . Por exemplo, é bem possível reduzir um problema NP-completo difícil de resolver, como o problema de satisfatibilidade booleana, a 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 produza zero apenas se houver uma solução. No entanto, isso não chega a muito, porque embora possamos resolver o novo problema, realizar a redução é tão difícil quanto resolver o problema antigo. Da mesma forma, uma redução computando uma função não computável pode reduzir um problema indecidível a um decidível. Como Michael Sipser aponta na Introdução à Teoria da Computação : "A redução deve ser fácil, em relação à complexidade dos problemas típicos da classe [...] Se a própria redução fosse difícil de computar, uma solução fácil ao completo problema não geraria necessariamente uma solução fácil para os problemas que se reduzem a ele. "

Portanto, a noção apropriada de redução depende da classe de complexidade que está sendo estudada. Ao estudar a classe de complexidade NP e as classes mais duras, tais como a hierarquia polinomial , reduções de tempo polinomial são usados. Ao estudar classes dentro de P, como NC e NL , reduções de espaço de log são usadas. As reduções também são usadas na teoria da computabilidade para mostrar se os problemas são ou não resolvidos por máquinas; neste caso, as reduções são restritas apenas a funções computáveis .

No caso de problemas de otimização (maximização ou minimização), muitas vezes pensamos em termos de redução preservando a aproximação . Suponha que temos dois problemas de otimização, de modo que as instâncias de um problema podem ser mapeadas nas instâncias do outro, de forma que soluções quase ótimas para as instâncias do último problema possam ser transformadas de volta para produzir soluções quase ótimas para o primeiro. Desta forma, se temos um algoritmo de otimização (ou algoritmo de aproximação ) que encontra soluções quase ótimas (ou ótimas) para instâncias do problema B, e uma redução preservadora de aproximação eficiente do problema A para o problema B, por composição obtemos uma otimização algoritmo que produz soluções quase ótimas para instâncias do problema A. Reduções de preservação de aproximação são freqüentemente usadas para provar a dureza dos resultados de aproximação : se algum problema de otimização A é difícil de aproximar (sob alguma suposição de complexidade) dentro de um fator melhor do que α para alguns α, e há uma redução preservando a aproximação β do problema A para o problema B, podemos concluir que o problema B é difícil de aproximar dentro do fator α / β.

Exemplos

Exemplo detalhado

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

Para obter uma contradição, suponha que R é um decisor para E . Usaremos isso para produzir um decisor S para H (que sabemos não existir). Dada a entrada M e w (uma máquina de Turing e alguma string de entrada), defina S ( M , w ) com o seguinte comportamento: S cria uma máquina de Turing N que aceita apenas se a string de entrada para N for w e M parar na entrada w , e não para de outra forma. O decisor S pode agora avaliar R ( N ) para verificar se a linguagem aceita por N está vazia. Se R aceita N , então a linguagem aceita por N está vazia, então em particular M não pára na entrada w , então S pode rejeitar. Se R rejeita N , então a linguagem aceita por N não é vazia, então M pára na entrada w , então S pode aceitar. Assim, se tivéssemos um decisor R para E , seríamos capazes de produzir um decisor S para o problema de parada H ( M , w ) para qualquer máquina M e entrada w . Visto que sabemos que tal S não pode existir, segue-se que a linguagem E também é indecidível.

Veja também

Referências

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e 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 .
  • ER Griffor: Handbook of Computability Theory, North Holland, 1999, ISBN  978-0-444-89882-1 .