Nonuniform proof systems: a new framework to describe nonuniform and probabilistic complexity classes
- 12 August 1991
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 85 (2) , 305-331
- https://doi.org/10.1016/0304-3975(91)90185-5
Abstract
No abstract availableKeywords
This publication has 18 references indexed in Scilit:
- A decisive characterization of BPPInformation and Control, 1986
- On small generatorsTheoretical Computer Science, 1984
- BPP and the polynomial hierarchyInformation Processing Letters, 1983
- Some consequences of non-uniform conditions on uniform classesTheoretical Computer Science, 1983
- A low and a high hierarchy within NPJournal of Computer and System Sciences, 1983
- Strong nondeterministic polynomial-time reducibilitiesTheoretical Computer Science, 1982
- Reductions on NP and P-selective setsTheoretical Computer Science, 1982
- AlternationJournal of the ACM, 1981
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNPTheory of Computing Systems, 1979
- The polynomial-time hierarchyTheoretical Computer Science, 1976