Abstract | ||
---|---|---|
We extend the # operator in a natural way and derive new types of counting complexity classes. While in the case of #C classes (where C could be some circuit-based class like NC1) only proofs for acceptance of some input are being counted, one can also count proofs for rejection. The Zap-C complexity classes we propose here implement this idea. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1016/j.tcs.2015.08.041 | Theoretical Computer Science |
Keywords | Field | DocType |
Circuits,Branching programs,Counting,Arithmetization | Complexity class,Discrete mathematics,Polynomial,Duality (optimization),Mathematical proof,Operator (computer programming),Electronic circuit,Mathematics,Bounded function,Branching (version control) | Conference |
Volume | Issue | ISSN |
610 | PA | 0304-3975 |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Olga Dorzweiler | 1 | 0 | 0.34 |
Thomas Flamm | 2 | 0 | 0.34 |
Andreas Krebs | 3 | 3 | 4.15 |
Michael Ludwig | 4 | 3 | 1.80 |