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

11/02/2014
by   Igor Razgon, et al.
0

In this paper we prove a space lower bound of n^Ω(k) for non-deterministic (syntactic) read-once branching programs ( nrobps) on functions expressible as cnfs with treewidth at most k of their primal graphs. This lower bound rules out the possibility of fixed-parameter space complexity of nrobps parameterized by k. We use lower bound for nrobps 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset