Truth table reduction

Truth table reduction

In computability theory, a truth table reduction is a reduction from one set of natural numbers to another. Truth table reductions are less powerful than Turing reductions, since not every Turing reduction between sets can be performed by a truth table reduction, but every truth table reduction can be performed by a Turing reduction. A weak truth table reduction is a related type of reduction which is so named because it weakens the constraints placed on a truth table reduction, and provides a weaker equivalence classification; as such, a "weak truth table reduction" can actually be more powerful than a truth table reduction, and perform a reduction which is not performable by truth table.

A Turing reduction from a set "B" to a set "A" computes the membership of a single element in "A" by asking questions about the membership of various elements in "B" during the computation; it may adaptively determine which questions it asks based upon answers to previous questions. In contrast, a truth table reduction or a weak truth table reduction must present all of its (finitely many) oracle queries at the same time. In a truth table reduction, the reduction also gives a boolean function (a truth table) which, when given the answers to the queries, will produce the final answer of the reduction. In a weak truth table reduction, the reduction uses the oracle answers as a basis for further computation which may depend on the given answers but may not ask further questions of the oracle.

Equivalently, a weak truth table reduction is a Turing reduction for which the use of the reduction is bounded by a computable function. For this reason, they are sometimes referred to as bounded Turing (bT) reductions rather than as weak truth table (wtt) reductions.

Properties

As every truth table reduction is a Turing reduction, if "A" is truth table reducible to "B" ("A" ≤tt "B"), then "A" is also Turing reducible to "B" ("A" ≤T "B"). Considering also many-one reducibility and weak truth table reducibility, one gets the following chain of implications:
* A leq_m B Rightarrow A leq_{tt} B Rightarrow A leq_{wtt} B Rightarrow A leq_T B; many-one reducibility implies truth table reducibility, which in turn implies weak truth table reducibility, which in turn implies Turing reducibility.


Wikimedia Foundation. 2010.

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”