# 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 .