Computational complexity, speedable and levelable sets

DOI10.2307/2271876zbMATH Open0401.68020OpenAlexW2069890413MaRDI QIDQ4185801FDOQ4185801

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

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

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
• On \(0'\)-computable reals
• Strong enumeration reducibilities
• 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
• 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
• Classification of the index sets of low \([n]^ p\) and high \([n]^ p\)
• 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
• Degree structures of conjunctive reducibility
• Some lowness properties and computational complexity sequences
• 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)