On the read-once property of branching programs and CNFs of bounded treewidth

preprint2015arXivOpen access

Abstract

In this paper we prove a space lower bound of nΩ(k)n^{Ω(k)} for non-deterministic (syntactic) read-once branching programs ({\sc nrobp}s) on functions expressible as {\sc cnf}s with treewidth at most kk of their primal graphs. This lower bound rules out the possibility of fixed-parameter space complexity of {\sc nrobp}s parameterized by kk. We use lower bound for {\sc nrobp}s to obtain a quasi-polynomial separation between Free Binary Decision Diagrams and Decision Decomposable Negation Normal Forms, essentially matching the existing upper bound introduced by Beame et al. and thus proving the tightness of the latter.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.