Positive and negative proofs for circuits and branching programs (Q896677)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Positive and negative proofs for circuits and branching programs |
scientific article; zbMATH DE number 6519454
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Positive and negative proofs for circuits and branching programs |
scientific article; zbMATH DE number 6519454 |
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
