Hierarchy of complexity of computation of partial functions with values 0 and 1
From MaRDI portal
Publication:1149431
DOI10.1007/BF01158327zbMath0454.03017MaRDI QIDQ1149431
Publication date: 1981
Published in: Mathematical Notes (Search for Journal in Brave)
03D15: Complexity of computation (including implicit computational complexity)
03D20: Recursive functions and relations, subrecursive hierarchies
03D10: Turing machines and related notions
03D55: Hierarchies of computability and definability
Cites Work
- Unnamed Item
- Hierarchies of Turing machines with restricted tape alphabet size
- Techniques for separating space complexity classes
- Relating refined space complexity classes
- A hierarchy for nondeterministic time complexity
- Two-Tape Simulation of Multitape Turing Machines
- A Machine-Independent Theory of the Complexity of Recursive Functions
- The Operator Gap