Some lowness properties and computational complexity sequences
From MaRDI portal
Publication:1255315
DOI10.1016/0304-3975(78)90007-5zbMath0401.68021MaRDI QIDQ1255315
Robert I. Soare, Victor L. Bennison
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
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
03D25: Recursively (computably) enumerable sets and degrees
Related Items
NON-SPLITTINGS OF SPEEDABLE SETS, On self-reducibility and weak P-selectivity, Automorphisms of the lattice of recursively enumerable sets: Orbits, Congruence relations on lattices of recursively enumerable sets, Characterization of Recursively Enumerable Sets with Supersets Effectively Isomorphic to all Recursively Enumerable Sets, Recursively enumerable complexity sequences and measure independence, Recursively enumerable sets and degrees
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
