Some lowness properties and computational complexity sequences
From MaRDI portal
Publication:1255315
DOI10.1016/0304-3975(78)90007-5zbMath0401.68021OpenAlexW2035558335MaRDI QIDQ1255315
Victor L. Bennison, Robert I. Soare
Publication date: 1978
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(78)90007-5
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25)
Related Items
Characterization of Recursively Enumerable Sets with Supersets Effectively Isomorphic to all Recursively Enumerable Sets, Automorphisms of the lattice of recursively enumerable sets: Orbits, Recursively enumerable sets and degrees, Recursively enumerable complexity sequences and measure independence, NON-SPLITTINGS OF SPEEDABLE SETS, On self-reducibility and weak P-selectivity, Congruence relations on lattices of recursively enumerable sets
Cites Work
- Unnamed Item
- Unnamed Item
- On some games which are relevant to the theory of recursively enumerable sets
- The use of lists in the study of undecidable problems in automata theory
- Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
- Automorphisms of the lattice of recursively enumerable sets. Part II: Low sets
- Recursively enumerable complexity sequences and measure independence
- On complexity properties of recursively enumerable sets
- On degrees of unsolvability and complexity properties
- Computational complexity, speedable and levelable sets
- Automorphisms of the lattice of recursively enumerable sets
- A Machine-Independent Theory of the Complexity of Recursive Functions
- The degrees of hyperhyperimmune sets
- Degrees of recursively enumerable sets which have no maximal supersets
- A Dichotomy of the Recursively Enumerable Sets
- Computational speed-up by effective operators
- Recursive Properties of Abstract Complexity Classes
