Redução por tabela verdade

Em teoria da computabilidade, uma redução por tabela-verdade é uma redução de um conjunto de números naturais para outro. Como uma "ferramenta", é mais fraca do que a redução de Turing, uma vez que nem toda redução de Turing entre conjuntos pode ser realizada por uma redução por tabela-verdade, mas cada redução por tabela-verdade pode ser realizada por uma redução de Turing. Pela mesma razão, é dita ser uma redutibilidade mais forte do que a Turing-reductibilidade porque implica na Turing-redutibilidade. Uma redução por tabela-verdade fraca, é um tipo relacionado de redução que é assim chamado porque enfraquece as restrições postas sobre uma redução por tabela-verdade, e fornece uma classificação de equivalência mais fraca; como tal, uma "redução por tabela-verdade fraca" pode realmente ser mais poderosa do que uma redução por tabela-verdade como uma "ferramenta", e realizar uma redução que não é realizada pela tabela-verdade.

Uma redução de Turing de um conjunto B para um conjunto A calcula a pertinência de um único elemento em A, fazendo perguntas sobre a pertinência de vários elementos em B durante a computação; ela pode adaptativamente determinar quais questões são perguntadas com base em respostas às perguntas anteriores. Em contraste, uma redução por tabela-verdade ou uma redução por tabela-verdade fraca deve apresentar todas as suas consultas “oraculares” ao mesmo tempo. Em uma redução por tabela-verdade, a redução também dá uma função booleana que, quando dado as respostas para as perguntas, irá produzir a resposta final da redução. Em um redução tabela-verdade fraca, a redução usa as respostas como uma base para cálculos posteriores que pode depender das respostas dadas. Equivalentemente, uma redução tabela-verdade fraca é uma redução de Turing que o uso da redução é delimitada por uma função calculável. Por esta razão, eles são muitas vezes referidas como reduções de Turing limitada e não como reduções tabela verdade fraca.

Definição

uma linguagem A é redutível em tempo polinomial por tabela verdade a uma linguagem B, escrito $A\leq _{tt}^{p}B$, se existe uma função computável em tempo polinomial g mapeando uma entrada X em uma número polinomial de entradas Y1; : : : ; Yk e uma função f computável tambem em tempo polinomial (chamada predicado tabela-verdade), que depende de X e que mapeia ${0,1}^{k}$ para ${0,1}$ tal como $X\in A\iff f(x_{B}(Y_{1}),...,x_{B}(Y_{k}))=1$ onde $x_{B}(X)$ é a função característica para a linguagem B

Propriedades

Como toda redução tabela verdade é uma redução Turing, se A é a tabela verdade redutível a B, então A também é Turing redutível a B. Considerando, também, uma uma redutibilidade, muitos um redutibilidade e fraco redutibilidade tabela de verdade, tem-se a seguinte cadeia de implicações: $A\leq _{1}B\Rightarrow A\leq _{m}B\Rightarrow A\leq _{tt}B\Rightarrow A\leq _{wtt}B\Rightarrow A\leq _{T}B$

Referências

1. 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
2. Fortnow L., Reingold N. PP is Closed Under Truth-Table Reductions