Redução (teoria da recursão)

Na Teoria da computação, muitos tipos de reduções são estudadas. A motivação para tal, é a seguinte: dado os conjuntos de números naturais A e B, é possível efetivamente converter um método de decisão para B em um método de decisão para A? Se a resposta para essa questão for positiva, então pode se dizer que A é redutível a B.

O estudo de noções de redutibilidade é motivado pelo estudo da decisão de problemas. Para noção de muitos problemas de redutibilidade, se algum conjunto não-computável é redutível a um conjunto A, então A deve ser não computável. Isto nos dá uma técnica muito poderosa para provar que muitos conjuntos de problemas são não-computáveis.

Relações de redutibilidade

Uma relação de redutibilidade é uma relação binária em conjuntos de números naturais que são:

Reflexiva : todo conjunto é redutível a ele mesmo.
Transitiva : Se um conjunto A é redutível a um conjunto B e um conjunto B é redutível a um conjunto C, então A é redutível a C.

As noções de redutibilidade estudadas na teória da computação têm a propriedade informal de que A é redutível a B se e somente se algum (possivelmente até mesmo não efetivo) procedimento de decisão para B pode ser efetivamente convertido para um procedimento de decisão para A. As diferentes relações de redutibilidade variam de métodos para métodos, que permitem ou não o uso de processos de conversão.

Redutibilidade de Turing

A mais fundamental noção de redutibilidade é a redutibilidade de Turing. Um conjunto A de números naturais é Turing Redutível para um conjunto B se e somente se existe uma máquina de Turing que, quando rodando sobre B, computa a função característica de A. Equivalentemente, A é Turing redutível para b se e somente se existe um algoritmo para computação da função característica para A, dado que o algoritmo é do tipo que responde corretamente questões do tipo "n está em B"?

Redutibilidade de Turing serve como uma linha divisora para outros tipos de redubitilidade porque, de acordo com a tese de Church-Turing, é o caso mais genérico de relação de redutibilidade que é efetivo. Relações de redutibilidade que implicam na redutibilidade de Turing são conhecidas com redutibilidades fortes, enquanto aquelas que relações que são implicadas pela redutibilidade de Turing são conhecidas como redutibilidades fracas. Equivalentemente, uma redutibilidade forte é uma relação em que os graus deste redutibilidade formam uma equivalência fina com os graus da redutibilidade de Turing, enquanto que redutibilidade forte é uma relação em que os graus formam uma equivalência mais grosseira.

Redutibilidades mais Fortes que a Redutibilidade de Turing

As redutibilidades fortes incluem:

Redutibilidade um para um: A é 'um-para-um' redutível para B se existe uma função um para um computável f com A(x) = B(f(x)) para todo x.
Redutibilidade muitos para um: A é 'muitos-para-um' redutível para B se existe uma função computável f com A(x) = B(f(x)) para todo x.
Redutibilidade Tabela Verdade: A é 'tabela-verdade' reduzível para B se A é Turing redutível para B por apenas uma (oracle) Máquina de Turing que produz uma função total relativa para "oracle".
Redutibilidade Tabela Verdade Fraca: A é 'tabela-verdade-fraca' redutível para B se existe uma redução de Turing de B para A e uma função recursiva com limites para uso. Mesmo que A seja 'tabela-verdade' redutível para B, A é também 'tabela-verdade-fraca' redutível para B.
Redutibilidade Positiva: A é 'Positivamente' redutível para B se e somente se A é 'tabela-verdade' redutível para B de forma que um pode computar para cada x a formula consistente de átomos da forma B(0), B(1), ... uma vez que esses termos são combinados por E's e OU's, onde o E de a e b é 1 se a = 1 e b = 1 e assim em diante.
Redutibilidade Disjuntiva: Parecido com a redução positiva com o adicional que só são permitidos OU's.
Redutibilidade Conjuntiva: Parecido com a redução positiva com o adicional que só são permitidos E's.
Redutibilidade Linear: Parecido com a redução positiva com o adicional que todos os átomos da forma B(n) são combinados por OU's exclusivos. Em outras palavras, A é linear redutível para B se e somente se uma função computável computa para cada x um conjunto finito F(x) dado como uma lista explícita de números tais que x ∈ A se e somente se F(x) contém um número impar de elementos de B.

Muitos destes conceitos foram introduzidos por POST (1944). Post estava procurando por um conjunto recursivamente enumerável mas não recursivo para o qual o problema da parada poderia ser redutível. Como não conseguiu construir tal conjunto em 1944, trabalhou em problemas análogos para várias redutibilidades que ele introduziu. Essas redutibilidades foram então produtos de muita pesquisa, e muitas relações entre eles são hoje conhecidas.

Reduções fortes na teoria da complexidade

As reduções fortes listadas acima restringem a maneira no qual a informação pode ser acessada por um procedimento de decisão, mas não reduz o limite computacional disponível. Logo, se um conjunto A é decidível, então A é redutível para algum conjunto B em alguma das redutibilidades fortes listadas acima, mesmo que A não seja decidível em tempo polinomial ou exponencial. Isto é aceitável no estudo da teoria da recursão, que está interessada na teoria da computação, mas não é aceitável na teoria da complexidade computacional, que está interessada em estudar conjuntos que podem ser decididos em certos limites assintóticos de recursos (tempo).

A mais comum redutibilidade na teoria da complexidade é a redutibilidade para tempo polinomial. Um conjunto A é redutível em tempo polinomial a um conjunto B se existe uma função em tempo polinomial que para cada n, n está em A, se e somente se f(n) está em B. A redutibilidade é, essencialmente, um recurso-limite da versão da redutibilidade muitos-para-um.

Redutibilidades mais fracas que a Redutibilidade de Turing

Mesmo que redutibilidade de Turing sejm a forma mais geral de redutibilidade que é efetiva, redutibilidade fraca são também comumente estudadas. Estas redutibilidades são relacionadas com a definição de conjuntos além da aritmética ou da teoria dos conjuntos. Isto inclui:

Redução Aritmética: Um conjunto A é aritmeticamente reduzível em um conjunto B se é definido através do modelo padrão da aritmética de Peano com um predicado extra para B. Equivalentemente, de acordo com o teorema de POST, A é aritmético em B se e somente se A é Turing redutível para B(n), o enésimo pulo de Turing de B, para algum número natural N. A hierarquia aritmética nos dá uma fina classificação da redução aritmética.
Redução HiperAritmética: A é um conjunto hiperAritmético em um conjunto B se A é \Delta^1_1 definido (veja hierarquia analítica) através do modelo padrão da aritmética de Peano com um predicado extra para B. Equivalentemente, A é hiperAritmético em B se e somente se A é Turing Redutível para B(α), o αésimo (alfaésimo) pulo de Turing sobre B, para algum número ordinal α B-recursivo.
Construição relativa: Um conjunto A é relativamente construível de um conjunto B se A está em L(B), o menor modelo transitivo de do conjunto teórico ZFC contendo B e todos os ordinários.

Referências

Bibliografia

(Em Inglês)

K. Ambos-Spies and P. Fejer, 2006. "Degrees of Unsolvability." Unpublished preprint.
P. Odifreddi, 1989. Classical Recursion Theory, North-Holland. ISBN 0-444-87295-7
P. Odifreddi, 1999. Classical Recursion Theory, Volume II, Elsevier. ISBN 0-444-50205-X
E. Post, 1944, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, volume 50, pages 284–316.
H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
G Sacks, 1990. Higher Recursion Theory, Springer-Verlag. ISBN 3-540-19305-7