Upper semilattice of recursively enumerable sQ-degrees

DOI10.1007/BF01985061MaRDI QIDQ1803017zbMATH OpenFDO

Authors Roland Sh. Omanadze

Publication date 29 June 1993

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01985061

zbMATH Keywords

\(sQ\)-reducibilityabstract complexity propertiesdensityspeedabilityupper semilattice of recursively enumerable \(sQ\)- degrees

Mathematics Subject Classification ID

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

Review text

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.

Recommendations

• scientific article; zbMATH DE number 4202251
• Relations between certain reducibilities
• On distributivity of the upper semilattices of the degrees below 0'
• Upper semilattice of recursively enumerable Q-degrees
• On \(sQ\)-completeness of recursively enumerable sets

Cites work

• Computational complexity, speedable and levelable sets
• Effectively nowhere simple sets
• scientific article; zbMATH DE number 4059379 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Nowhere simple sets and the lattice of recursively enumerable sets
• On complexity properties of recursively enumerable sets
• On the Cartesian subalgebras of a free Lie sum of Lie algebras
• Three theorems on the degrees of recursively enumerable sets
• Upper semilattice of recursively enumerable Q-degrees

Cited in

(12)

• Upper semilattice of recursively enumerable Q-degrees
• Relations between certain reducibilities
• sQ₁-degrees of computably enumerable sets
• scientific article; zbMATH DE number 4055595 (Why is no real title available?)
• scientific article; zbMATH DE number 4081536 (Why is no real title available?)
• \(Q _{1}\)-degrees of c.e. sets
• Immunity properties and strong positive reducibilities
• r‐Maximal sets and Q1,N‐reducibility
• On quasi-reducibility for c.e. sets. I: The structure of the Q-degrees and the sQ-degrees
• On minimal pairs of quasi-degrees
• Non-empty open intervals of computably enumerable sQ₁-degrees
• Strong enumeration reducibilities

This page was built for publication: Upper semilattice of recursively enumerable sQ-degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1803017)