Generalized lowness and highness and probabilistic complexity classes
- 1 December 1989
- journal article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 22 (1) , 37-45
- https://doi.org/10.1007/bf02088291
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- Are there interactive protocols for co-NP languages?Information Processing Letters, 1988
- Does co-NP have short interactive proofs?Information Processing Letters, 1987
- Complexity and StructureLecture Notes in Computer Science, 1986
- Trading group theory for randomnessPublished by Association for Computing Machinery (ACM) ,1985
- The knowledge complexity of interactive proof-systemsPublished by Association for Computing Machinery (ACM) ,1985
- BPP and the polynomial hierarchyInformation Processing Letters, 1983
- A low and a high hierarchy within NPJournal of Computer and System Sciences, 1983
- Robustness of probabilistic computational complexity classes under definitional perturbationsInformation and Control, 1982
- Some observations on the probabilistic algorithms and NP-hard problemsInformation Processing Letters, 1982
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977