Upper semilattice of recursively enumerable sQ-degrees. (English. Russian original) Zbl 0788.03060

Algebra Logic 30, No. 4, 265-271 (1991); translation from Algebra Logika 30, No. 4, 405-413 (1991).
A set \(A\) is called \(sQ\)-reducible to \(B\) if there exist recursive functions \(f\) and \(g\) such that, for all \(x\), \(x \in A\) iff \(W_{f(x)} \subseteq B\) (i.e. \(A \leq_ QB)\) and, for all \(y\), \(y \in W_{f(x)}\) implies \(y \leq g(x)\). The author studies various properties of the upper semilattice of recursively enumerable \(sQ\)-degrees and relationships to abstract complexity properties such as speedability in the sense of M. Blum and I. Marques [J. Symb. Logic 38, 579-593 (1973; Zbl 0335.02024)]. For instance, a density theorem is proven, and relationships with \(wtt\)- and \(T\)-degrees are discussed.


03D25 Recursively (computably) enumerable sets and degrees
03D30 Other degrees and reducibilities in computability and recursion theory
03D15 Complexity of computation (including implicit computational complexity)


Zbl 0335.02024
Full Text: DOI


[1] H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967). · Zbl 0183.01401
[2] R. Sh. Omanadze, ”On the upper semilattice of recursively enumerable Q-degrees,” Algebra Logika,23, No. 2, 175–184 (1984). · Zbl 0586.03034
[3] A. N. Degtev, Enumerable Sets and Reducibility [in Russian], Tyumen’ (1988).
[4] R. A. Shore, ”Nowhere simple sets and the lattice of recursively enumerable sets,” J. Symb. Logic,43, No. 2, 322–330 (1978). · Zbl 0398.03029
[5] R. Sh. Omanadze, ”Q-reducibility and nowhere simple sets,” Soobshch. Akad. Nauk Gruz. SSR,127, No. 1, 29–32 (1987). · Zbl 0649.03030
[6] C. E. M. Yates, ”Three theorems on the degree of recursively enumerable sets,” Duke Math. J.,32, 461–468 (1965). · Zbl 0134.00805
[7] D. Miller and J. R. Remmel, ”Effectively nowhere simple sets,” J. Symb. Logic,49, 129–136 (1984). · Zbl 0598.03036
[8] M. Blum and I. Marques, ”On complexity properties of recursively enumerable sets,” J. Symb. Logic,38, No. 4, 579–593 (1973). · Zbl 0335.02024
[9] R. I. Soare, ”Computational complexity, speedable and levelable sets,” J. Symb. Logic,42, No. 4, 545–562 (1977). · Zbl 0401.68020
[10] R. I. Soare, Recursively Enumerable Sets and Degrees, Springer, Berlin (1987). · Zbl 0667.03030
[11] S. S. Marchenko, ”On truth-table degrees of maximal sets,” Mat. Zametki,20, No. 3, 373–381 (1976).
[12] S. D. Denisov, ”On m-degrees of recursively enumerable sets,” Algebra Logika,9, No. 4, 422–427 (1970). · Zbl 0246.17007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.