Positive and negative proofs for circuits and branching programs
DOI10.1016/J.TCS.2015.08.041zbMATH Open1347.68158OpenAlexW1789118945WikidataQ113863214 ScholiaQ113863214MaRDI QIDQ896677FDOQ896677
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
Recommendations
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Title not available (Why is that?)
- Nondeterministic \(NC^1\) computation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Nondeterministic Space is Closed under Complementation
- The method of forced enumeration for nondeterministic automata
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Title not available (Why is that?)
- Making Nondeterminism Unambiguous
- Gap-definable counting classes
- Unambiguity of circuits
- Constant width planar computation characterizes ACC\(^{0}\)
- A New Pebble Game that Characterizes Parallel Complexity Classes
- Circuit Definitions of Nondeterministic Complexity Classes
Cited In (5)
- Worst-case groundness analysis using positive Boolean functions
- Proof complexity of monotone branching programs
- 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)
