Truth-table reduction

In computability theory a truth-table reduction is a type of reduction from a decision problem $A$ to a decision problem $B$. To solve a problem in $A$, the reduction describes the answer to $A$ as a boolean formula or truth table of some finite number of queries to $B$.

Truth-table reductions are related to Turing reductions, and strictly weaker. (That is, 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 Turing reduction from a set B to a set A computes the membership of a single element in B by asking questions about the membership of various elements in A 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 formula (a truth table) that, when given the answers to the queries, will produce the final answer of the reduction.

Truth-table reductions appear in a paper by Emil Post published in 1944.

Weak truth-table reductions

A weak truth-table reduction is one where 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. It 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 as a "tool", and perform a reduction that is not performable by truth table. 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 one-one reducibility, many-one reducibility and weak truth-table reducibility,

$A\leq _{1}B\Rightarrow A\leq _{m}B\Rightarrow A\leq _{tt}B\Rightarrow A\leq _{wtt}B\Rightarrow A\leq _{T}B$,

or in other words, one-one reducibility implies many-one reducibility, which implies truth-table reducibility, which in turn implies weak truth-table reducibility, which in turn implies Turing reducibility.

Furthermore, A is truth-table reducible to B if and only if A is Turing reducible to B via a total functional on $2^{\omega }$. The forward direction is trivial and for the reverse direction suppose $\Gamma$ is a total computable functional. To build the truth-table for computing A(n) simply search for a number m such that for all binary strings $\sigma$ of length m $\Gamma ^{\sigma }(n)$ converges. Such an m must exist by Kőnig's lemma since $\Gamma$ must be total on all paths through $2^{<\omega }$. Given such an m it is a simple matter to find the unique truth-table that gives $\Gamma ^{\sigma }(n)$ when applied to $\sigma$. The forward direction fails for weak truth-table reducibility.

References

• 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