Some Observations on Separating Complexity Classes

DOI10.1137/0220015zbMath0724.68039OpenAlexW1986693286MaRDI QIDQ3212285

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

polynomial timerelativizationcomplexity classespolynomial spacePSPACENPBPPAMthe PB-operator, uniform witnessesthe polynomial- time hierarchy

Mathematics Subject Classification ID

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

Related Items (2)

On collapsing the polynomial-time hierarchy ⋮ Circuit size relative to pseudorandom oracles

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