Mostrar código-fonte de 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 <math>A \leq_{tt}^p B</math>, 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 <math>{0,1}^k</math> para <math>{0,1}</math> tal como <math>X \in A \iff f(x_B(Y_1),...,x_B(Y_k)) = 1</math> onde <math>x_B(X)</math> é 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:
<math>A \leq_1 B \Rightarrow A \leq_m B \Rightarrow A \leq_{tt} B \Rightarrow A \leq_{wtt} B \Rightarrow A \leq_T B</math>

{{Referências}}
# 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
# Fortnow L., Reingold N. [http://people.cs.uchicago.edu/~fortnow/papers/pptt.pdf PP is Closed Under Truth-Table Reductions]

{{Portal3|Matemática}}
[[Categoria:Teoria da computação|*]]
[[Categoria:Complexidade]]