Positive and negative proofs for circuits and branching programs (Q896677)
From MaRDI portal
!
WARNING
This is the item page for this Wikibase entity, intended for internal use and editing purposes.
Please use the normal view instead:
scientific article; zbMATH DE number 6519454
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.9710657000541688
0 references
0.7363713979721069
0 references
0.7140756249427795
0 references
0.7113940715789795
0 references
