Positive and negative proofs for circuits and branching programs

We extend the # operator in a natural way and derive new types of counting complexity classes. While in the case of #C#C classes (where CC could be some circuit-based class like NC1NC1) only proofs for acceptance of some input are being counted, one can also count proofs for rejection. The Zap-CZap-C complexity classes we propose here implement this idea.We show that in certain cases Zap-CZap-C lies between #C#C and Gap-CGap-C which could help understanding the relationship between #C#C and Gap-CGap-C. In particular we consider Zap-NC1Zap-NC1 and polynomial size branching programs of bounded and unbounded width. Finally we argue about negative proofs in Turing machines and how those relate to open questions.