On collapsing the polynomial-time hierarchy
Author:
- Ronald V. BookRBRonald V. Book
- 9 December 1994
- journal article
- Published by Elsevier in Information Processing Letters
- Vol. 52 (5) , 235-237
Abstract
No abstract availableThis publication has 9 references indexed in Scilit:
- An observation on probability versus randomness with applications to complexity classesTheory of Computing Systems, 1994
- Some Observations on Separating Complexity ClassesSIAM Journal on Computing, 1991
- Probabilistic complexity classes and lownessJournal of Computer and System Sciences, 1989
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchyJournal of Computer and System Sciences, 1989
- Randomness, relativizations, and polynomial reducibilities1986
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- A Theory of Program Size Formally Identical to Information TheoryJournal of the ACM, 1975
- Process complexity and effective random testsJournal of Computer and System Sciences, 1973
- The definition of random sequencesInformation and Control, 1966