Positive and negative proofs for circuits and branching programs (Q896677)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Positive and negative proofs for circuits and branching programs |
scientific article |
Statements
Positive and negative proofs for circuits and branching programs (English)
0 references
10 December 2015
0 references
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.
0 references
circuits
0 references
counting
0 references
arithmetization
0 references
number of positive proofs
0 references
number of negative proofs
0 references
branching programs
0 references
0 references
