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 classes (where C could be some circuit-based class like NC 1 ) 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.We show that in certain cases Zap- C lies between # C and Gap- C which could help understanding the relationship between # C and Gap- C . In particular we consider Zap- NC 1 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.