Truth-table reducibility

$tt$-reducibility, diagram reducibility

A particular kind of algorithmic reducibility. Let $A$ and $B$ be two sets of natural numbers. One says that $A$ is truth-table reducible to $B$ (notation $A\leq_{tt}B$) if there is an algorithm $f$ that constructs for any natural number $a$ a Boolean function $\phi(x_1,\ldots,x_n)$ (the function is given, for instance, by its table; the number of arguments of the function may depend on $a$) and numbers $b_1,\ldots,b_n$ such that $a\in A$ is equivalent to the truth of $\phi(b_1\in B,\ldots,b_n\in B)$.

The relation $\leq_{tt}$ is a pre-order on the set of all subsets of the natural numbers. To the relation $\leq_{tt}$ corresponds an equivalence relation $\equiv_{tt}$, namely $A\equiv_{tt}B$ if $A\leq_{tt}B$ and $B\leq_{tt}A$. The equivalence classes for this relation are called truth-table degrees (or $tt$-degrees); they form an upper semi-lattice.

In the theory of algorithms more special kinds of $tt$-reducibility are also considered, for instance bounded $tt$-reducibility ($btt$-reducibility), defined by the additional requirement that the number of arguments of the function $\phi$ does not depend on $a$. If one simply takes the function $x_1$ for $\phi$, the reducibility is called many-one reducibility (notation: $\leq_m$). Intermediate reducibilities between $\leq_{tt}$ and $\leq_m$, in particular all those mentioned above, are sometimes called reducibilities of truth-table type [2].

References

[1]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165
[2]	A.N. Degtev, "Reducibilities of tabular type in the theory of algorithms" Russian Math. Surveys , 34 : 3 (1979) pp. 155–192 Uspekhi Mat. Nauk , 34 : 3 (1979) pp. 137–168

Comments

The various notions of reducibilities in recursion theory have found their resource-bounded analogues in the theory of computational complexity. In these theories the algorithm $f$ is subjected to the further requirement that it can be computed in polynomial time or even logarithmic space.

References

[a1]	R.E. Ladner, N.A. Lynch, A.L. Selman, "A comparison of polynomial time reducibilities" Theor. Comp. Sc. , 1 (1975) pp. 103–123
[a2]	R.I. Soare, "Recursively enumerable sets and degrees, a study of computable functions and generated sets" , Springer (1987)