Truth-table reduction

In <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a> a truth-table reduction is a type of <a href="/facts/Reduction_(complexity)/IVWF7a1c">reduction</a> from a <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a> 
 
 
 
 A
 
 
 {\displaystyle A}
 
 to a decision problem 
 
 
 
 B
 
 
 {\displaystyle B}
 
. To solve a problem in 
 
 
 
 A
 
 
 {\displaystyle A}
 
, the reduction describes the answer to 
 
 
 
 A
 
 
 {\displaystyle A}
 
 as a <a href="/facts/Boolean_function/uT7E8pqC">boolean formula</a> or <a href="/facts/Truth_table/4KsmArDW">truth table</a> of some finite number of queries to 
 
 
 
 B
 
 
 {\displaystyle B}
 
.
Truth-table reductions are related to <a href="/facts/Turing_reduction/qczcQTbz">Turing reductions</a>, 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) <a href="/facts/Oracle_(computer_science)/6ScMuvvY">oracle</a> queries at the same time. In a truth-table reduction, the reduction also gives a <a href="/facts/Boolean_function/uT7E8pqC">boolean formula</a> (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 <a href="/facts/Emil_Post/Hl2CKCxw">Emil Post</a> published in 1944.

Truth-table reduction open-in-new

Truth-table reduction