Gap-definable counting classes
- 28 February 1994
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 48 (1) , 116-148
- https://doi.org/10.1016/s0022-0000(05)80024-8
Abstract
No abstract availableKeywords
This publication has 19 references indexed in Scilit:
- Two remarks on the power of countingPublished by Springer Nature ,2005
- Counting classes: thresholds, parity, mods, and fewnessTheoretical Computer Science, 1992
- Turing machines with few accepting computations and low sets for PPJournal of Computer and System Sciences, 1992
- PP is as Hard as the Polynomial-Time HierarchySIAM Journal on Computing, 1991
- Arithmetization: A new method in structural complexity theorycomputational complexity, 1991
- On the power of parity polynomial timeTheory of Computing Systems, 1990
- Probabilistic complexity classes and lownessJournal of Computer and System Sciences, 1989
- On the construction of parallel computers from various bases of boolean functionsTheoretical Computer Science, 1986
- The complexity of computing the permanentTheoretical Computer Science, 1979
- The polynomial-time hierarchyTheoretical Computer Science, 1976