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

countingcircuitsbranching programsarithmetizationnumber of negative proofsnumber of positive proofs

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• Making Nondeterminism Unambiguous
• Nondeterministic Space is Closed under Complementation
• Nondeterministic NC^1 computation
• The method of forced enumeration for nondeterministic automata
• Unambiguity of circuits

Cited in

(5)

• Proof complexity of monotone branching programs
• Worst-case groundness analysis using positive Boolean functions
• Succinct certification of monotone circuits
• Computing the best-case energy complexity of satisfying assignments in monotone circuits
• 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)