Abstract
We introduce the concept of a generic relation for algorithmic problems, which preserves the property of being decidable for a problem for almost all inputs and possesses the transitive property. As distinct from the classical m-reducibility relation, the generic relation under consideration does not possess the reflexive property: we construct an example of a recursively enumerable set that is generically incomparable with itself. We also give an example of a set that is complete with respect to the generic relation in the class of recursively enumerable sets.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
REFERENCES
I. Kapovich, A. Myasnikov, P. Schupp, and V. Shpilrain, “Generic-case complexity, decision problems in group theory, and random walks,” J. Alg., 264, No. 2, 665-694 (2003).
I. Kapovich, A. Myasnikov, P. Schupp, and V. Shpilrain, “Average-case complexity and decision problems in group theory,” Adv. Math., 190, No. 2, 343-359 (2005).
J. D. Hamkins and A. Miasnikov, “The halting problem is decidable on a set of asymptotic probability one,” Notre Dame J. Form. Log., 47, No. 4, 515-524 (2006).
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967).
S. A. Cook, “The complexity of theorem-proving procedures,” ACM, Proc. 3d Ann. ACM Sympos. Theory Computing (Shaker Heights, Ohio 1971) (1971), pp. 151-158.
C. G. jun. Jockusch, and P. E. Schupp, “Generic computability, Turing degrees, and asymptotic density,” J. London Math. Soc., II. Ser., 85, No. 2, 472-490 (2012).
G. Igusa, “The generic degrees of density-1 sets, and a characterization of the hyperarithmetic reals,” J. Symb. Log., 80, No. 4, 1290-1314 (2015).
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by Russian Science Foundation, project 14-11-00085.
Translated from Algebra i Logika, Vol. 55, No. 5, pp. 587-596, September-October, 2016.
Rights and permissions
About this article
Cite this article
Rybalov, A.N. A Generic relation on Recursively Enumerable Sets. Algebra Logic 55, 387–393 (2016). https://doi.org/10.1007/s10469-016-9410-9
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10469-016-9410-9