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

arXiv: https://arxiv.org/abs/1407.0491 · HTML: https://mlsanity.com/paper/1407.0491/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2014.

## Built on by (most cited first, 1 of 1)

- [A canonical generalization of OBDD](https://mlsanity.com/paper/2604.05537/) (2026)

## Abstract (arXiv)

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