Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
Copyright policy )Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
Summary: Branching programs are a well-established computation model for Boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model \(M\) is the test whether a given BP is really a BP of model \(M\). Here it is proved that the consistency test is co-NP-complete for nondeterministic (parity) graph-driven BP1s. Moreover, a lower bound technique for nondeterministic graph-driven BP1s is presented. The method generalizes a technique for the well-structured model and is applied in order to answer in the affirmative the open question whether the model of nondeterministic graph-driven BP1s is a proper restriction of nondeterministic BP1s (with respect to polynomial size).
- TU Dortmund University Germany
Computational complexity, nondeterminism, lower bounds, Complexity classes (hierarchies, relations among complexity classes, etc.), Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Models of computation (Turing machines, etc.), read-once branching programs
Computational complexity, nondeterminism, lower bounds, Complexity classes (hierarchies, relations among complexity classes, etc.), Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Models of computation (Turing machines, etc.), read-once branching programs
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!