This article is cited in 3 scientific papers (total in 3 papers)
On ways of characterizing complete sets
V. K. Bulitko
The traditional method for constructing criteria for completeness with respect to reducibility is by describing the property of (in general, weakened) productiveness satisfied by the complement of a set which is complete with respect to the given reducibility. Originally this property was tied to the reducibility of a creative set to the complete set. Such a method appeals directly to the universality of the creative set in the class of all recursively enumerable sets.
However, for several reducibilities it is possible to determine the completeness of a recursively enumerable set from the fact that a certain set of degree below the degree of the creative sets is reducible to the given set. This second, “test” set is, of course, not recursively enumerable. In addition, in place of the property of effective nonrecursive enumerability which productive sets have, it is possible to substitute variants of the property of diagonal nonrecursiveness, although not for all reducibilities.
In this paper we examine the connection between these two approaches – specifically, between different weakenings of the property of productiveness on the one hand, and diagonal nonrecursiveness on the other – and we present results obtained by these methods for Turing and truth-table reducibilities.
PDF file (1581 kB)
Mathematics of the USSR-Izvestiya, 1992, 38:2, 225–249
V. K. Bulitko, “On ways of characterizing complete sets”, Izv. Akad. Nauk SSSR Ser. Mat., 55:2 (1991), 227–253; Math. USSR-Izv., 38:2 (1992), 225–249
Citation in format AMSBIB
\paper On ways of characterizing complete sets
\jour Izv. Akad. Nauk SSSR Ser. Mat.
\jour Math. USSR-Izv.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
V. K. Bulitko, “Letter to the editor”, Russian Acad. Sci. Izv. Math., 41:1 (1993), 185–185
R. Sh. Omanadze, “Complexity properties of recursively enumerable sets and $sQ$-completeness”, Math. Notes, 62:3 (1997), 356–359
R. Sh. Omanadze, “Complexity properties of recursively enumerable sets and $bsQ$-completeness”, Math. Notes, 68:4 (2000), 476–480
|Number of views:|