as a boolean formula or truth table of some finite number of queries to
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.
Truth-table reductions appear in a paper by Emil Post published in 1944.
[1] 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.
For this reason, they are sometimes referred to as bounded Turing (bT) reductions rather than as weak truth-table (wtt) reductions.
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).
To build the truth-table for computing A(n) simply search for a number m such that for all binary strings
Given such an m it is a simple matter to find the unique truth-table that gives
The forward direction fails for weak truth-table reducibility.
This mathematical logic-related article is a stub.