Algorithmic reducibility

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)

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