Positive and negative proofs for circuits and branching programs

DOI10.1016/J.TCS.2015.08.041MaRDI QIDQ896677zbMATH OpenOpenAlexWikidataFDO

Authors Olga Dorzweiler, Thomas Flamm, A. Krebs, Michael Ludwig

Publication date 10 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.08.041

zbMATH Keywords

arithmetizationbranching programscircuitscountingnumber of negative proofsnumber of positive proofs

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

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.

Recommendations

• Positive and negative proofs for circuits and branching programs
• scientific article; zbMATH DE number 1507219
• On arithmetic branching programs
• Semantical counting circuits
• Counting classes: Thresholds, parity, mods, and fewness

Cites work

• A New Pebble Game that Characterizes Parallel Complexity Classes
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Circuit Definitions of Nondeterministic Complexity Classes
• Constant width planar computation characterizes ACC\(^{0}\)
• Gap-definable counting classes
• scientific article; zbMATH DE number 3916181 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 2196509 (Why is no real title available?)
• Making Nondeterminism Unambiguous
• Nondeterministic NC^1 computation
• Nondeterministic Space is Closed under Complementation
• The method of forced enumeration for nondeterministic automata
• Unambiguity of circuits

Cited in

(5)

• Proof complexity of monotone branching programs
• Succinct certification of monotone circuits
• Computing the best-case energy complexity of satisfying assignments in monotone circuits
• Worst-case groundness analysis using positive Boolean functions
• Positive and negative proofs for circuits and branching programs

This page was built for publication: Positive and negative proofs for circuits and branching programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896677)