|
This article is cited in 2 scientific papers (total in 2 papers)
A generic relation on recursively enumerable sets
A. N. Rybalovab a Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, ul. Pevtsova 13, Omsk, 644099 Russia
b Omsk State Technical University, pr. Mira 11, Omsk, 644050 Russia
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.
Keywords:
generic relation, complete set, recursively enumerable set.
Received: 13.04.2016
Citation:
A. N. Rybalov, “A generic relation on recursively enumerable sets”, Algebra Logika, 55:5 (2016), 587–596; Algebra and Logic, 55:5 (2016), 387–393
Linking options:
https://www.mathnet.ru/eng/al763 https://www.mathnet.ru/eng/al/v55/i5/p587
|
|