Relativized counting classes: Relations among thresholds, parity, and mods
Open Access
- 1 February 1991
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 42 (1) , 76-96
- https://doi.org/10.1016/0022-0000(91)90040-c
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- On complete problems for NP∩CoNPPublished by Springer Nature ,2005
- Complexity classes without machines: On complete languages for UPTheoretical Computer Science, 1988
- On the construction of parallel computers from various bases of boolean functionsTheoretical Computer Science, 1986
- The complexity of combinatorial problems with succinct input representationActa Informatica, 1986
- On the unique satisfiability problemInformation and Control, 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
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- The polynomial-time hierarchyTheoretical Computer Science, 1976
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975