Encyclopedia

Truth-table reduction

Concept in theoretical computer science

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated February 3, 2026

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.

01Weak 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.

02Properties

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. 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.

Watch videos about Truth-table reductionExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Truth-table reduction”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.