Namespaces
Variants
Actions

Difference between revisions of "Algorithmic reducibility"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX done)
 
Line 1: Line 1:
One of the basic concepts in the theory of algorithms (cf. [[Algorithms, theory of|Algorithms, theory of]]) and its applications. Its background was the fact that solvability (and unsolvability) of many algorithmic problems (cf. [[Algorithmic problem|Algorithmic problem]]) is not established directly, but rather by reducing some algorithmic problem, already demonstrated to be unsolvable, to the problem in question, or by reducing the latter problem to some other one which has already been solved. Thus, the problem of homotopy of paths in a polyhedron is shown to be unsolvable by reducing the problem of equality of words in the corresponding fundamental group to this problem.
+
One of the basic concepts in the [[Algorithms, theory of|theory of algorithms]] and its applications. Its background was the fact that solvability (and unsolvability) of many [[algorithmic problem]]s is not established directly, but rather by reducing some algorithmic problem, already demonstrated to be unsolvable, to the problem in question, or by reducing the latter problem to some other one which has already been solved. Thus, the problem of homotopy of paths in a polyhedron is shown to be unsolvable by reducing the problem of equality of words in the corresponding fundamental group to this problem.
  
 
In what follows, the simplest examples of algorithmic reducibility of number-theoretical predicates and functions (i.e. those defined on natural numbers) will be presented:
 
In what follows, the simplest examples of algorithmic reducibility of number-theoretical predicates and functions (i.e. those defined on natural numbers) will be presented:
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a0118701.png" /></td> </tr></table>
+
P(x) \equiv Q(2x+1) \ ,
 
+
$$
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a0118702.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a0118703.png" /> are predicates. The problem of solving the predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a0118704.png" />, that is, of establishing the truth or falsehood of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a0118705.png" /> for different values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a0118706.png" />, is reduced to the problem of solving <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a0118707.png" /> — or,  "P is reduced to Q" , for short. One may also say that the set of truths of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a0118708.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a0118709.png" />, is reduced to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187010.png" />.
+
where $P$ and $Q$ are predicates. The problem of solving the predicate $P$, that is, of establishing the truth or falsehood of $P$ for different values of $x$, is reduced to the problem of solving $Q$ — or,  "$P$ is reduced to $Q$" , for short. One may also say that the set of truths of $P$, i.e. $\{x : P(x) \}$, is reduced to $\{ x : Q(x) \}$.
  
 
Let
 
Let
 +
$$
 +
f(x) = \prod_{u=1}^{x!} \prod_{y=1}^u g(u,y) \ ,
 +
$$
 +
where $f$ and $g$ are number-theoretic functions. The problem of computation of the function $f$ is reduced to the computation of $g$ or, for short, $f$ is reduced to $g$.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187011.png" /></td> </tr></table>
+
The concept of algorithmic reducibility was given a more exact form by A.M. Turing: If, roughly speaking, some [[Turing machine]] transforms a sequence of encoded values of the function $g$ into a sequence of encoded values of the function $f$, then $f$ is [[Turing reducibility|Turing reduced]] ($T$-reduced) to $g$, denoted $f \le_T g$. S.C. Kleene [[#References|[1]]] formulated the related concept of relative computability with the aid of recursive systems of equations. After arithmetization, each algorithmic problem is reduced to the problem of computing some number-theoretic function $f$. If $f$ is $T$-reduced to $g$ and $g$ is reduced to $f$, then one says that $f$ and $g$ have the same degree of unsolvability or that $f \equiv_T g$. The relation $\le_T$ is both reflexive and transitive. Thus, all functions (and sets of natural numbers or their characteristic predicates) are subdivided into equivalence classes, known as ''Turing degrees'' or $T$-degrees [[#References|[3]]]. Most algorithmic problems considered in logic and in mathematics are expressible as problems of membership in enumerable sets of constructive objects. In this context the study of enumerable sets was initiated in the 1940s by E.L. Post [[#References|[2]]]; he introduced certain special kinds of algorithmic reducibility, in addition to Turing's kind, and formulated the problem of reducibility as follows: Can various enumerable unsolvable sets be reduced (according to Turing) to each other? It was subsequently established that the enumerable sets form an infinite, very rich system of $T$-degrees. This was supplemented by discovering the so-called priority method, which is extensively employed in the theory of algorithms.
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187013.png" /> are number-theoretic functions. The problem of computation of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187014.png" /> is reduced to the computation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187015.png" /> or, for short, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187016.png" /> is reduced to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187017.png" />.
+
Subsequently, degrees of unsolvability found applications in other branches of mathematics as well. For instance, for all $T$-degrees $A$ and $B$ of enumerable sets, if $A \le B$, then there exists a finitely-determined group in which the problem of equality of words has degree $A$, while the conjugation problem has degree $B$. There is a close connection between degrees (concerning the different kinds of algorithmic reducibility) of enumerable sets and the rate of growth of the complexity of initial fragments of enumerable sets. A special kind of reducibility — polynomial reducibility or p-reducibility (reducibility with some limitation imposed on time) — is employed in proving the universal character of combinatorial optimization problems from various branches of mathematics [[#References|[5]]]; for more details on this subject see [[#References|[1]]]. The methods of measure theory [[#References|[1]]], and the [[Forcing method|forcing method]] [[#References|[4]]] have in turn been used in the study of degrees.
 
 
The concept of algorithmic reducibility was given a more exact form by A.M. Turing: If, roughly speaking, some [[Turing machine|Turing machine]] transforms a sequence of encoded values of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187018.png" /> into a sequence of encoded values of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187019.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187020.png" /> is reduced to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187021.png" />. S.C. Kleene [[#References|[1]]] formulated the related concept of relative computability with the aid of recursive systems of equations. After arithmetization, each algorithmic problem is reduced to the problem of computing some number-theoretic function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187022.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187023.png" /> is reduced to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187024.png" /> according to Turing, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187025.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187026.png" /> is reduced to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187028.png" />, then one says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187030.png" /> have the same degree of unsolvability or that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187031.png" />. The relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187032.png" /> is both reflexive and transitive. Thus, all functions (and sets of natural numbers or their characteristic predicates) are subdivided into equivalence classes, known as Turing degrees or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187034.png" />-degrees [[#References|[3]]]. Most algorithmic problems considered in logic and in mathematics are expressible as problems of membership in enumerable sets of constructive objects. In this context the study of enumerable sets was initiated in the 1940s by E.L. Post [[#References|[2]]]; he introduced certain special kinds of algorithmic reducibility, in addition to Turing's kind, and formulated the problem of reducibility as follows: Can various enumerable unsolvable sets be reduced (according to Turing) to each other? It was subsequently established that the enumerable sets form an infinite, very rich system of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187035.png" />-degrees. This was supplemented by discovering the so-called priority method, which is extensively employed in the theory of algorithms.
 
 
 
Subsequently, degrees of unsolvability found applications in other branches of mathematics as well. For instance, for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187036.png" />-degrees <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187038.png" /> of enumerable sets, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187039.png" />, then there exists a finitely-determined group in which the problem of equality of words has degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187040.png" />, while the conjugation problem has degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011870/a01187041.png" />. There is a close connection between degrees (concerning the different kinds of algorithmic reducibility) of enumerable sets and the rate of growth of the complexity of initial fragments of enumerable sets. A special kind of reducibility — polynomial reducibility or p-reducibility (reducibility with some limitation imposed on time) — is employed in proving the universal character of combinatorial optimization problems from various branches of mathematics [[#References|[5]]]; for more details on this subject see [[#References|[1]]]. The methods of measure theory [[#References|[1]]], and the [[Forcing method|forcing method]] [[#References|[4]]] have in turn been used in the study of degrees.
 
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  E.L. Post,  "Recursively enumerable sets of positive integers and their decision problems"  ''Bull. Amer. Math. Soc.'' , '''50'''  (1944)  pp. 284–316</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  S.C. Kleene,  E.L. Post,  "The upper semi-lattice of degrees of recursive unsolvability"  ''Ann. of Math. (2)'' , '''59''' :  3  (1954)  pp. 379–407</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.L. Selman,  "Applications of forcing to the degree-theory of the arithmetical hierarchy"  ''Proc. London Math. Soc. (3)'' , '''25'''  (1972)  pp. 586–602</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  R.M. Karp,  "Reducibility among combinatorial problems"  R.E. Miller (ed.)  J.W. Tatcher (ed.) , ''Complexity of Computer Computations. Proc. Symp. IBM'' , Plenum  (85–103)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  E.L. Post,  "Recursively enumerable sets of positive integers and their decision problems"  ''Bull. Amer. Math. Soc.'' , '''50'''  (1944)  pp. 284–316</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  S.C. Kleene,  E.L. Post,  "The upper semi-lattice of degrees of recursive unsolvability"  ''Ann. of Math. (2)'' , '''59''' :  3  (1954)  pp. 379–407</TD></TR>
 +
<TR><TD valign="top">[4]</TD> <TD valign="top">  A.L. Selman,  "Applications of forcing to the degree-theory of the arithmetical hierarchy"  ''Proc. London Math. Soc. (3)'' , '''25'''  (1972)  pp. 586–602</TD></TR>
 +
<TR><TD valign="top">[5]</TD> <TD valign="top">  R.M. Karp,  "Reducibility among combinatorial problems"  R.E. Miller (ed.)  J.W. Tatcher (ed.) , ''Complexity of Computer Computations. Proc. Symp. IBM'' , Plenum  (85–103)</TD></TR>
 +
</table>
  
  
Line 26: Line 32:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.I. Soare,  "Recursively enumerable sets and degrees, a study of computable functions and generated sets" , Springer  (1986)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  S.G. Simpson,  "Degrees of unsolvability: a survey of results"  J. Barwise (ed.) , ''Handbook of mathematical logic'' , North-Holland  (1977)  pp. 631–652</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  R.I. Soare,  "Recursively enumerable sets and degrees, a study of computable functions and generated sets" , Springer  (1986)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  S.G. Simpson,  "Degrees of unsolvability: a survey of results"  J. Barwise (ed.) , ''Handbook of mathematical logic'' , North-Holland  (1977)  pp. 631–652</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}

Latest revision as of 19:26, 22 January 2016

One of the basic concepts in the theory of algorithms and its applications. Its background was the fact that solvability (and unsolvability) of many algorithmic problems is not established directly, but rather by reducing some algorithmic problem, already demonstrated to be unsolvable, to the problem in question, or by reducing the latter problem to some other one which has already been solved. Thus, the problem of homotopy of paths in a polyhedron is shown to be unsolvable by reducing the problem of equality of words in the corresponding fundamental group to this problem.

In what follows, the simplest examples of algorithmic reducibility of number-theoretical predicates and functions (i.e. those defined on natural numbers) will be presented: $$ P(x) \equiv Q(2x+1) \ , $$ where $P$ and $Q$ are predicates. The problem of solving the predicate $P$, that is, of establishing the truth or falsehood of $P$ for different values of $x$, is reduced to the problem of solving $Q$ — or, "$P$ is reduced to $Q$" , for short. One may also say that the set of truths of $P$, i.e. $\{x : P(x) \}$, is reduced to $\{ x : Q(x) \}$.

Let $$ f(x) = \prod_{u=1}^{x!} \prod_{y=1}^u g(u,y) \ , $$ where $f$ and $g$ are number-theoretic functions. The problem of computation of the function $f$ is reduced to the computation of $g$ or, for short, $f$ is reduced to $g$.

The concept of algorithmic reducibility was given a more exact form by A.M. Turing: If, roughly speaking, some Turing machine transforms a sequence of encoded values of the function $g$ into a sequence of encoded values of the function $f$, then $f$ is Turing reduced ($T$-reduced) to $g$, denoted $f \le_T g$. S.C. Kleene [1] formulated the related concept of relative computability with the aid of recursive systems of equations. After arithmetization, each algorithmic problem is reduced to the problem of computing some number-theoretic function $f$. If $f$ is $T$-reduced to $g$ and $g$ is reduced to $f$, then one says that $f$ and $g$ have the same degree of unsolvability or that $f \equiv_T g$. The relation $\le_T$ is both reflexive and transitive. Thus, all functions (and sets of natural numbers or their characteristic predicates) are subdivided into equivalence classes, known as Turing degrees or $T$-degrees [3]. Most algorithmic problems considered in logic and in mathematics are expressible as problems of membership in enumerable sets of constructive objects. In this context the study of enumerable sets was initiated in the 1940s by E.L. Post [2]; he introduced certain special kinds of algorithmic reducibility, in addition to Turing's kind, and formulated the problem of reducibility as follows: Can various enumerable unsolvable sets be reduced (according to Turing) to each other? It was subsequently established that the enumerable sets form an infinite, very rich system of $T$-degrees. This was supplemented by discovering the so-called priority method, which is extensively employed in the theory of algorithms.

Subsequently, degrees of unsolvability found applications in other branches of mathematics as well. For instance, for all $T$-degrees $A$ and $B$ of enumerable sets, if $A \le B$, then there exists a finitely-determined group in which the problem of equality of words has degree $A$, while the conjugation problem has degree $B$. There is a close connection between degrees (concerning the different kinds of algorithmic reducibility) of enumerable sets and the rate of growth of the complexity of initial fragments of enumerable sets. A special kind of reducibility — polynomial reducibility or p-reducibility (reducibility with some limitation imposed on time) — is employed in proving the universal character of combinatorial optimization problems from various branches of mathematics [5]; for more details on this subject see [1]. The methods of measure theory [1], and the forcing method [4] have in turn been used in the study of degrees.

References

[1] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967)
[2] E.L. Post, "Recursively enumerable sets of positive integers and their decision problems" Bull. Amer. Math. Soc. , 50 (1944) pp. 284–316
[3] S.C. Kleene, E.L. Post, "The upper semi-lattice of degrees of recursive unsolvability" Ann. of Math. (2) , 59 : 3 (1954) pp. 379–407
[4] A.L. Selman, "Applications of forcing to the degree-theory of the arithmetical hierarchy" Proc. London Math. Soc. (3) , 25 (1972) pp. 586–602
[5] R.M. Karp, "Reducibility among combinatorial problems" R.E. Miller (ed.) J.W. Tatcher (ed.) , Complexity of Computer Computations. Proc. Symp. IBM , Plenum (85–103)


Comments

References

[a1] R.I. Soare, "Recursively enumerable sets and degrees, a study of computable functions and generated sets" , Springer (1986)
[a2] S.G. Simpson, "Degrees of unsolvability: a survey of results" J. Barwise (ed.) , Handbook of mathematical logic , North-Holland (1977) pp. 631–652
How to Cite This Entry:
Algorithmic reducibility. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Algorithmic_reducibility&oldid=15508
This article was adapted from an original article by A.A. Muchnik (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article