Teoria da Computabilidade e Complexidade: Redutibilidade
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ção 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.