Redução (teoria da recursão): diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 10:
* 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 é
== Redutibilidade de Turing ==
Linha 17:
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
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.
Linha 25:
As redutibilidades fortes incluem:
* Redutibilidade um para um: A é 'um-para-um'
* Redutibilidade muitos para um: A é 'muitos-para-um'
* Redutibilidade Tabela Verdade: A é 'tabela-verdade' reduzível para B se A é Turing
* Redutibilidade Tabela Verdade Fraca: A é 'tabela-verdade-fraca'
* 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
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
=== Reduções fortes na teoria da complexidade ===
Linha 42:
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
== Redutibilidades mais fracas que a Redutibilidade de Turing ==
| |||