Some results on relativized deterministic and nondeterministic time hierarchies

DOI10.1016/0022-0000(81)90017-9zbMath0482.68040OpenAlexW2028776719MaRDI QIDQ1162808

Shlomo Moran

Publication date: 1981

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(81)90017-9

zbMATH Keywords

determinism versus nondeterminismoracle computationrelativized time hierarchiestime and space complexity measures for relativized multitape Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Relativized alternation and space-bounded computation ⋮ Downward translations of equality ⋮ $$P\mathop{ =}\limits^{?}NP$$

Cites Work

• Relativization of questions about log space computability
• Relativization of the Theory of Computational Complexity
• Separating Nondeterministic Time Complexity Classes
• On the Computational Complexity of Algorithms
• Relativized questions involving probabilistic algorithms
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item