View source for Truth-table reducibility

''<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t0943802.png" />-reducibility, diagram reducibility''

A particular kind of [[Algorithmic reducibility|algorithmic reducibility]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t0943803.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t0943804.png" /> be two sets of natural numbers. One says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t0943805.png" /> is truth-table reducible to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t0943806.png" /> (notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t0943807.png" />) if there is an algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t0943808.png" /> that constructs for any natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t0943809.png" /> a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438010.png" /> (the function is given, for instance, by its table; the number of arguments of the function may depend on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438011.png" />) and numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438012.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438013.png" /> is equivalent to the truth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438014.png" />.

The relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438015.png" /> is a pre-order on the set of all subsets of the natural numbers. To the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438016.png" /> corresponds an equivalence relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438017.png" />, namely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438018.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438020.png" />. The equivalence classes for this relation are called truth-table degrees (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438022.png" />-degrees); they form an upper semi-lattice.

In the theory of algorithms more special kinds of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438023.png" />-reducibility are also considered, for instance bounded <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438025.png" />-reducibility (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438027.png" />-reducibility), defined by the additional requirement that the number of arguments of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438028.png" /> does not depend on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438029.png" />. If one simply takes the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438030.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438031.png" />, the reducibility is called many-one reducibility (notation: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438032.png" />). Intermediate reducibilities between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438034.png" />, in particular all those mentioned above, are sometimes called reducibilities of truth-table type [[#References|[2]]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  H. Rogers jr.,   "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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</TD></TR></table>



====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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094380/t09438035.png" /> is subjected to the further requirement that it can be computed in polynomial time or even logarithmic space.

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