Upper semilattice of recursively enumerable sQ-degrees (Q1803017)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Upper semilattice of recursively enumerable sQ-degrees |
scientific article |
Statements
Upper semilattice of recursively enumerable sQ-degrees (English)
0 references
29 June 1993
0 references
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.
0 references
\(sQ\)-reducibility
0 references
upper semilattice of recursively enumerable \(sQ\)- degrees
0 references
abstract complexity properties
0 references
speedability
0 references
density
0 references