Positive and negative proofs for circuits and branching programs
type: Item
instance of: scholarly article
title: Positive and negative proofs for circuits and branching programs
zbMATH Open document ID: 1347.68158
author: Olga Dorzweiler
author: Thomas Flamm
author: A. Krebs
author: Michael Ludwig
published in: Theoretical Computer Science
publication date: 2015-12-10T00:00:00Z
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.
reviewed by: Mihai Prunescu
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 6519454
zbMATH Keywords: circuits
zbMATH Keywords: counting
zbMATH Keywords: arithmetization
zbMATH Keywords: number of positive proofs
zbMATH Keywords: number of negative proofs
zbMATH Keywords: branching programs
MaRDI profile type: Publication
full work available at URL: j.tcs.2015.08.041
OpenAlex ID: W1789118945
Wikidata QID: Q113863214
cites work: Q5465356
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: Nondeterministic \(NC^1\) computation
cites work: Gap-definable counting classes
cites work: Constant width planar computation characterizes ACC\(^{0}\)
cites work: Nondeterministic Space is Closed under Complementation
cites work: Q3691587
cites work: Unambiguity of circuits
cites work: Q4298260
cites work: Making Nondeterminism Unambiguous
cites work: The method of forced enumeration for nondeterministic automata
cites work: Circuit Definitions of Nondeterministic Complexity Classes
cites work: Q4393484
cites work: A New Pebble Game that Characterizes Parallel Complexity Classes
DOI: 10.1016/J.TCS.2015.08.041
description: scientific article; zbMATH DE number 6519454