The Boolean Hierarchy II: Applications
- 1 February 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 18 (1) , 95-111
- https://doi.org/10.1137/0218007
Abstract
No abstract availableThis publication has 13 references indexed in Scilit:
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy CollapsesSIAM Journal on Computing, 1988
- The Boolean Hierarchy I: Structural PropertiesSIAM Journal on Computing, 1988
- Complexity classes without machines: On complete languages for UPTheoretical Computer Science, 1988
- Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-CompleteSIAM Journal on Computing, 1987
- The boolean hierarchy: Hardware over NPPublished by Springer Nature ,1986
- On sparse oracles separating feasible complexity classesPublished by Springer Nature ,1986
- Computation times of NP sets of different densitiesTheoretical Computer Science, 1984
- On the unique satisfiability problemInformation and Control, 1982
- A second step toward the polynomial hierarchyTheoretical Computer Science, 1979
- Tally languages and complexity classesInformation and Control, 1974