Positive and negative proofs for circuits and branching programs
The authors think that the negative proofs are a neglected aspect of counting. They introduce the notion of negative proof tree. Based on some complexity class C, Zap-C is the class of functions counting positive and negative proofs. They prove that Zap-BWBP \(\subseteq\) Zap-NC\(_1\) \(\subseteq\) Zap-PBP.
scientific article; zbMATH DE number 6519454
scientific article