On the power of probabilistic polynomial time: P/sup NP(log)/ contained in PP
- 7 January 2003
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
No abstract availableKeywords
This publication has 8 references indexed in Scilit:
- Two remarks on the power of countingPublished by Springer Nature ,2005
- Turing machines with few accepting computations and low sets for PPJournal of Computer and System Sciences, 1992
- The complexity of optimization problemsJournal of Computer and System Sciences, 1988
- Structural Complexity IPublished by Springer Nature ,1988
- On truth-table reducibility to SAT and the difference hierarchy over NPPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- PNP [log n] and Sparse Turing-Complete Sets for NPPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- The complexity of facets (and some facets of complexity)Journal of Computer and System Sciences, 1984
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977