Hierarchy of complexity of computation of partial functions with values 0 and 1

DOI10.1007/BF01158327zbMath0454.03017MaRDI QIDQ1149431

Anatoly Petrivich Beltiukov

Publication date: 1981

Published in: Mathematical Notes (Search for Journal in Brave)

zbMATH Keywords

partial functionsTuring machinecomplexity classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10) Hierarchies of computability and definability (03D55)

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