Namespaces
Variants
Actions

Difference between revisions of "Truth-table reducibility"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX)
m (link)
 
Line 2: Line 2:
 
''$tt$-reducibility, diagram reducibility''
 
''$tt$-reducibility, diagram reducibility''
  
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)$.
+
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.
+
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 [[#References|[2]]].
+
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 17: Line 17:
  
 
====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>

Latest revision as of 21:57, 16 January 2016

$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
This article was adapted from an original article by A.L. Semenov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article