Open AccessQuasiminimal pairs for c.e. degrees of generic and coarse reducibilities
Author(s) -
Alexander Rybalov
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1441/1/012166
Subject(s) - turing , set (abstract data type) , computer science , recursively enumerable language , mathematics , discrete mathematics , recursively enumerable set , domain (mathematical analysis) , programming language , mathematical analysis
Generic approach to algorithmic problems in combinatorial group theory was suggested in 2003 by Kapovich, Myasnikov, Schupp and Shpilrain. This approach deals with algorithms, which solves algorithmic problems on ”most” of the inputs (i.e., on a generic set) instead of the entire domain and output undefined answer (do not halt) on the rest of inputs (a negligible set). Generic analog of Turing reducibility was introduced by Jockusch and Schupp in 2012. Later Hirschfeldt, Jockusch, Kuyper and Schupp defined coarse reducibility. In this paper we prove that there exist quasiminimal pairs for generic and coarse reducibilities of computably enumerable (c.e.) degrees. The work was supported by Russian Science Foundation, grant number 18-71-10028.