Computational complexity, speedable and levelable sets

DOI10.2307/2271876zbMath0401.68020OpenAlexW2069890413MaRDI QIDQ4185801

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) Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (28)

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

Cites Work

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

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