For CNFs that encode a ternary tree crossed with a path, Decision DNNFs whose conjunction gates split variables imbalancedly require size at least n^{Ω((1−α)√k)}, ruling out FPT-sized representations.
On the read-once property of branching programs and cnfs of bounded treewidth
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
citation-role summary
baseline 1
citation-polarity summary
fields
cs.CC 1years
2025 1verdicts
CONDITIONAL 1roles
baseline 1polarities
support 1representative citing papers
citing papers explorer
-
Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width
For CNFs that encode a ternary tree crossed with a path, Decision DNNFs whose conjunction gates split variables imbalancedly require size at least n^{Ω((1−α)√k)}, ruling out FPT-sized representations.