Difference between revisions of "Truth-table reducibility"
From Encyclopedia of Mathematics
(Importing text file) |
(TeX) |
||
| Line 1: | Line 1: | ||
| − | '' | + | {{TEX|done}} |
| + | ''$tt$-reducibility, diagram reducibility'' | ||
| − | A particular kind of [[Algorithmic reducibility|algorithmic reducibility]]. Let | + | A particular kind of [[Algorithmic reducibility|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 | + | 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 | + | 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 [[#References|[2]]]. |
====References==== | ====References==== | ||
| Line 13: | Line 14: | ||
====Comments==== | ====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 | + | 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==== | ====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> | <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> | ||
Revision as of 14:30, 11 August 2014
$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) |
How to Cite This Entry:
Truth-table reducibility. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Truth-table_reducibility&oldid=32838
Truth-table reducibility. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Truth-table_reducibility&oldid=32838
This article was adapted from an original article by A.L. Semenov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article