PP is as Hard as the Polynomial-Time Hierarchy
Open Access
- 1 October 1991
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 20 (5), 865-877
- https://doi.org/10.1137/0220053
Abstract
No abstract availableKeywords
This publication has 22 references indexed in Scilit:
- On the power of parity polynomial timePublished by Springer Science and Business Media LLC ,2005
- Probabilistic complexity classes and lownessJournal of Computer and System Sciences, 1989
- Relativizing complexity classes with sparse oraclesJournal of the ACM, 1986
- The polynomial-time hierarchy and sparse oraclesJournal of the ACM, 1986
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- BPP and the polynomial hierarchyInformation Processing Letters, 1983
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Complete sets and the polynomial-time hierarchyTheoretical Computer Science, 1976
- The polynomial-time hierarchyTheoretical Computer Science, 1976
- Relative complexity of checking and evaluatingInformation Processing Letters, 1976