Probabilistic machines, oracles, and quantifiers
- 1 January 1985
- book chapter
- Published by Springer Nature
- p. 159-192
- https://doi.org/10.1007/bfb0076220
Abstract
No abstract availableKeywords
This publication has 15 references indexed in Scilit:
- On relativized exponential and probabilistic complexity classesInformation and Control, 1986
- Sums of divisors, perfect numbers, and factoringPublished by Association for Computing Machinery (ACM) ,1984
- Relativized Questions Involving Probabilistic AlgorithmsJournal of the ACM, 1982
- 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
- On counting problems and the polynomial-time hierarchyTheoretical Computer Science, 1980
- Probabilistic algorithm for testing primalityJournal of Number Theory, 1980
- A second step toward the polynomial hierarchyTheoretical Computer Science, 1979
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971