Some Observations on Separating Complexity Classes

DOI10.1137/0220015MaRDI QIDQ3212285zbMATH OpenOpenAlexFDO

Authors Ronald V. Book

Publication date 1991

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

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

zbMATH Keywords

complexity classespolynomial spacepolynomial timePSPACErelativizationNPBPPAMthe PB-operator, uniform witnessesthe polynomial- time hierarchy

Mathematics Subject Classification ID

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

Recommendations

• Quantitative Relativizations of Complexity Classes
• On random oracle separations
• Positive Relativizations of Complexity Classes
• scientific article; zbMATH DE number 4077187
• Restricted relativizations of probabilistic polynomial time

Cited in

(9)

• scientific article; zbMATH DE number 2102762 (Why is no real title available?)
• Separating Complexity Classes Using Autoreducibility
• scientific article; zbMATH DE number 4114605 (Why is no real title available?)
• Circuit size relative to pseudorandom oracles
• On collapsing the polynomial-time hierarchy
• Relativized collapsing between BPP and PH under stringent oracle access
• Restricted relativizations of probabilistic polynomial time
• Fine separation of average time complexity classes
• scientific article; zbMATH DE number 4077187 (Why is no real title available?)

This page was built for publication: Some Observations on Separating Complexity Classes

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