Refining Nondeterminism in Relativizations of Complexity Classes

DOI10.1145/2402.322399MaRDI QIDQ3026342zbMATH OpenOpenAlexFDO

Authors Meirui Xu, John Doner, Ronald V. Book

Publication date 1983

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2402.322399

zbMATH Keywords

bounded oracle queriesinfinite hierarchies of relativized classesnondeterminismoracle machinesoracle setsrelativizations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Simplicity, Relativizations and Nondeterminism
• scientific article; zbMATH DE number 3885883
• scientific article; zbMATH DE number 4077187
• scientific article; zbMATH DE number 4011940
• Positive Relativizations of Complexity Classes

Cited in

(7)

• Mirror images and schemes for the maximal complexity of nondeterminism
• Nondeterministic separations
• Classes of bounded nondeterminism
• Dichotomy theorems for families of non-cofinal essential complexity
• Simplicity, Relativizations and Nondeterminism
• Relativizations of Unambiguous and Random Polynomial Time Classes
• Capturing Relativized Complexity Classes without Order

This page was built for publication: Refining Nondeterminism in Relativizations of Complexity Classes

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