Upper semilattice of recursively enumerable sQ-degrees (Q1803017): Difference between revisions

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 \textit{M. Blum} and \textit{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.