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.
Lower bounds for exact model counting and applications in probabilistic databases
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
citation-role summary
background 1
citation-polarity summary
fields
cs.CC 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 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.