A general method to construct oracles realizing given relationships between complexity classes

DOI10.1016/0304-3975(95)00161-1MaRDI QIDQ1351504zbMATH OpenOpenAlexFDO

Authors Nikolai K. Vereshchagin, Andrej Muchnik

Publication date 27 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(95)00161-1

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 3926244
• scientific article; zbMATH DE number 4011940
• scientific article; zbMATH DE number 4077187
• Oracles for Deterministic Versus Alternating Classes
• Relativized circuit complexity

Cites work

• scientific article; zbMATH DE number 3814972 (Why is no real title available?)
• scientific article; zbMATH DE number 1555957 (Why is no real title available?)
• An oracle builder's toolkit
• BPP and the polynomial hierarchy
• Complexity Measures for Public-Key Cryptosystems
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• Relativized Questions Involving Probabilistic Algorithms
• Sparse sets in NP-P: EXPTIME versus NEXPTIME

Cited in

(16)

• Arthur-Merlin games in Boolean decision trees
• scientific article; zbMATH DE number 4125012 (Why is no real title available?)
• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• Further oracles separating conjectures about incompleteness in the finite domain
• An oracle builder's toolkit
• An oracle separating \(\oplus P\) from \(PP^{PH}\)
• Separations by random oracles and ``almost classes for generalized reducibilities
• A tight relationship between generic oracles and type-2 complexity theory
• Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
• Easiness assumptions and hardness tests: Trading time for zero error
• Separating complexity classes with tally oracles
• Generic oracles, uniform machines, and codes
• Structural properties of oracle classes
• scientific article; zbMATH DE number 3992933 (Why is no real title available?)
• Tarski's theory of definability: Common themes in descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic
• Does the polynomial hierarchy collapse if onto functions are invertible?

This page was built for publication: A general method to construct oracles realizing given relationships between complexity classes

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