The complexity types of computable sets
From MaRDI portal
Publication:1190982
DOI10.1016/0022-0000(92)90018-EzbMath0746.68035MaRDI QIDQ1190982
Theodore A. Slaman, Wolfgang Maass
Publication date: 27 September 1992
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)
Cites Work
- On the structure of sets in NP and other complexity classes
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Time bounded random access machines
- Linear time transformations between combinatorial problems
- A characterization of complexity sequences
- On the Structure of Polynomial Time Reducibility
- “Helping”: several formalizations
- A Machine-Independent Theory of the Complexity of Recursive Functions
- An Overview of the Theory of Computational Complexity
- Computational speed-up by effective operators
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item