Truth table reduction

From Wikipedia, the free encyclopedia

In computability theory truth table reduction is a reduction which is stronger than many-one reduction but weaker than Turing reduction.

A Turing reduction from a set $A$ to a set $B$ solves each question $a \in A$ by asking the oracle $B$ a finite number of questions $b_1, \ldots, b_n \in B$ . The question $b_n \in B$ can depend on the answer of the previous question $b_{n-1} \in B$ . In a truth table reduction on the other hand the question $b_1, \ldots, b_n \in B$ only depend on $a \in A$ .

[edit] Properties

$A \leq B \Rightarrow A \leq_{tt} B$ , many-one reducibility implies truth table reducibility
$A \leq_{tt} B \Rightarrow A \leq_T B$ , truth table reducibility implies Turing reducibility