No small nondeterministic read-once branching programs for CNFs of bounded treewidth

Abstract

In this paper, given a parameter $k$, we demonstrate an infinite class of {\sc cnf}s of treewidth at most $k$ of their primary graphs such that the equivalent nondeterministic read-once branching programs ({\sc nrobp}s) are of size at least $n^{ck}$ for some universal constant $c$. Thus we rule out the possibility of fixed-parameter space complexity of {\sc nrobp}s parameterized by the smallest treewidth of the equivalent {\sc cnf}.

Prepared as a 12 pages conference version, thus some proofs are postponed to the appendix

Cited by in corpus (2)

• Non-FPT lower bounds for structural restrictions of decision DNNF
• Lower Bounds on the mim-width of Some Graph Classes