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.
Wikipedia contributors, "Truth-table reduction", Wikipedia, revision 1336381539, retrieved 20 November 2026, source, CC BY-SA 4.0.