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.

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,

${\displaystyle 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 ${\displaystyle 2^{\omega }}$ . The forward direction is trivial and for the reverse direction suppose ${\displaystyle \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 ${\displaystyle \sigma }$  of length m ${\displaystyle \Gamma ^{\sigma }(n)}$  converges. Such an m must exist by Kőnig's lemma since ${\displaystyle \Gamma }$  must be total on all paths through ${\displaystyle 2^{<\omega }}$ . Given such an m it is a simple matter to find the unique truth-table that gives ${\displaystyle \Gamma ^{\sigma }(n)}$  when applied to ${\displaystyle \sigma }$ . The forward direction fails for weak truth-table reducibility.

• 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