Turing machines with few accepting computations and low sets for PP
- 1 April 1992
- journal article
- research article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 44 (2) , 272-286
- https://doi.org/10.1016/0022-0000(92)90022-b
Abstract
No abstract availableThis publication has 12 references indexed in Scilit:
- Restricted relativizations of probabilistic polynomial timeTheoretical Computer Science, 1992
- Relativizing complexity classes with sparse oraclesJournal of the ACM, 1986
- The polynomial-time hierarchy and sparse oraclesJournal of the ACM, 1986
- On Circuit-Size Complexity and the Low Hierarchy in NPSIAM Journal on Computing, 1985
- Quantitative Relativizations of Complexity ClassesSIAM Journal on Computing, 1984
- A low and a high hierarchy within NPJournal of Computer and System Sciences, 1983
- Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisJournal of Computer and System Sciences, 1982
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- Relative complexity of checking and evaluatingInformation Processing Letters, 1976