Computational complexity, speedable and levelable sets

DOI10.2307/2271876MaRDI QIDQ4185801zbMATH OpenOpenAlexFDO

Authors Robert I. Soare

Publication date 1978

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2271876

zbMATH Keywords

Computational Complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recursively (computably) enumerable sets and degrees (03D25) Complexity of computation (including implicit computational complexity) (03D15)

Cites work

• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3387326 (Why is no real title available?)
• A Dichotomy of the Recursively Enumerable Sets
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Automorphisms of the lattice of recursively enumerable sets
• Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Degrees of recursively enumerable sets which have no maximal supersets
• Interpolation and embedding in the recursively enumerable degrees
• On Effective Procedures for Speeding Up Algorithms
• Recursive Properties of Abstract Complexity Classes
• Recursively enumerable sets of positive integers and their decision problems
• Recursively enumerable sets which are uniform for finite extensions
• Relativized Halting Problems
• Spectra and halting problems
• The class of recursively enumerable subsets of a recursively enumerabl e set
• The elementary theory of recursively enumerable sets
• Three theorems on the degrees of recursively enumerable sets

Cited in

(28)

• On strongly jump traceable reals
• Infima in the d.r.e. degrees
• Completely mitotic r. e. degrees
• Splitting theorems in recursion theory
• Classes of recursively enumerable sets and Q-reducibility
• On computational complexity and honest polynomial degrees
• Cappable recursively enumerable degrees and Post's program
• Strong enumeration reducibilities
• On \(0'\)-computable reals
• On self-reducibility and weak P-selectivity
• Upper semilattice of recursively enumerable Q-degrees
• On speedable and levelable vector spaces
• T-Degrees, Jump Classes, and Strong Reducibilities
• Characterization of Recursively Enumerable Sets with Supersets Effectively Isomorphic to all Recursively Enumerable Sets
• Classification of the index sets of low \([n]^ p\) and high \([n]^ p\)
• On the bounded quasi‐degrees of c.e. sets
• Speedable Left-c.e. Numbers
• Recursively enumerable sets and degrees
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Upper semilattice of recursively enumerable sQ-degrees
• Branching Degrees above low Degrees
• An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees
• Nonlevelable sets and immune sets in the accepting density hierarchy inNP
• Some lowness properties and computational complexity sequences
• Degree structures of conjunctive reducibility
• Effectively categorical abelian groups
• Some results about the R.E. degrees
• The approximation structure of a computably approximable real

This page was built for publication: Computational complexity, speedable and levelable sets

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