Oracles for Deterministic Versus Alternating Classes

DOI10.1137/0216042MaRDI QIDQ4205078zbMATH OpenOpenAlexFDO

Authors William Gasarch

Publication date 1987

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0216042

zbMATH Keywords

complexity classesoraclesrelativization

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4074484
• Relativizations comparing NP and exponential time
• scientific article; zbMATH DE number 4011940
• scientific article; zbMATH DE number 3995053
• scientific article; zbMATH DE number 3958736

Cited in

(13)

• Some hierarchies of relativized time-bounded complexity classes
• Relativized alternation and space-bounded computation
• A general method to construct oracles realizing given relationships between complexity classes
• Computations with oracles: Generalized selection
• Relativizations comparing NP and exponential time
• scientific article; zbMATH DE number 3926244 (Why is no real title available?)
• scientific article; zbMATH DE number 3958736 (Why is no real title available?)
• scientific article; zbMATH DE number 4074484 (Why is no real title available?)
• Simultaneous strong separations of probabilistic and unambiguous complexity classes
• scientific article; zbMATH DE number 3995053 (Why is no real title available?)
• scientific article; zbMATH DE number 227415 (Why is no real title available?)
• Downward translations of equality
• Bi-immunity results for cheatable sets

This page was built for publication: Oracles for Deterministic Versus Alternating Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4205078)