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

2014/11/02 by Igor Razgon, Razgon, Igor · 1 citation
Computer Science · #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.AI #cs.CC

paper · pdf · doi:10.48550/arxiv.1411.0264

Significantly simplified proof of the main combinatorial lemma. AROSRN replaced back by NROBP due to their equivalence

arxiv created 2015/07/26 · arxiv updated 2015/07/28

Abstract

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

Cited by

• Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width

Related

• No small nondeterministic read-once branching programs for CNFs of bounded treewidth
• The splitting power of branching programs of bounded repetition and CNFs of bounded width
• On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
• Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs
• Perspective on complexity measures targetting read-once branching programs