A time-space hierarchy between polynomial time and polynomial space

DOI10.1007/BF02835830zbMath0762.03017OpenAlexW2079637309MaRDI QIDQ4000863

Peter Clote

Publication date: 26 September 1992

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02835830

zbMATH Keywords

relativizationoraclecomplexity classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Computation models and function algebras

Cites Work

• On the scheme of induction for bounded arithmetic formulas
• Relativized alternation and space-bounded computation
• A taxonomy of problems with fast parallel algorithms
• Relativizing Time, Space, and Time-Space
• Relativization of questions about log space computability
• On restricted turing computability
• Subrecursiveness: Machine-independent notions of computability in restricted time and storage
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item