Positive and negative proofs for circuits and branching programs

DOI10.1016/j.tcs.2015.08.041zbMath1347.68158OpenAlexW1789118945WikidataQ113863214 ScholiaQ113863214MaRDI QIDQ896677

Andreas Krebs, Michael Ludwig, Thomas Flamm, Olga Dorzweiler

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 of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Computing the best-case energy complexity of satisfying assignments in monotone circuits ⋮ Succinct certification of monotone circuits

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The method of forced enumeration for nondeterministic automata
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Unambiguity of circuits
• Nondeterministic \(NC^1\) computation
• Gap-definable counting classes
• Constant width planar computation characterizes ACC\(^{0}\)
• Nondeterministic Space is Closed under Complementation
• A New Pebble Game that Characterizes Parallel Complexity Classes
• Circuit Definitions of Nondeterministic Complexity Classes
• Making Nondeterminism Unambiguous

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