Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.16012 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909644880871424 |
|---|---|
| author | Razgon, Igor |
| author_facet | Razgon, Igor |
| contents | Decomposable Negation Normal Forms \textsc{dnnf} [Darwiche, 'Decomposable Negation Normal Form', JACM, 2001] is a landmark Knowledge Compilation (\textsc{kc}) model, highly important both in \textsc{ai} and Theoretical Computer Science. Numerous restrictions of the model have been studied. In this paper we consider the restriction where all the gates are $α$-imbalanced that is, at most one input of each gate depends on more than $n^α$ variables (where $n$ is the number if variables of the function being represented).
The concept of imbalanced gates has been first considered in [Lai, Liu, Yin 'New canonical representations by augmenting OBDDs with conjunctive decomposition', JAIR, 2017]. We consider the idea in the context of representation of \textsc{cnf}s of bounded primal treewidth. We pose an open question as to whether \textsc{cnf}s of bounded primal treewidth can be represented as \textsc{fpt}-sized \textsc{dnnf} with $α$-imbalanced gates.
We answer the question negatively for Decision \textsc{dnnf} with $α$-imbalanced conjunction gates. In particular, we establish a lower bound of $n^{Ω((1-α) \cdot k)}$ for the representation size (where $k$ is the primal treewidth of the input \textsc{cnf}). The main engine for the above lower bound is a combinatorial result that may be of an independent interest in the area of parameterized complexity as it introduces a novel concept of bidimensionality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_16012 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width Razgon, Igor Computational Complexity Decomposable Negation Normal Forms \textsc{dnnf} [Darwiche, 'Decomposable Negation Normal Form', JACM, 2001] is a landmark Knowledge Compilation (\textsc{kc}) model, highly important both in \textsc{ai} and Theoretical Computer Science. Numerous restrictions of the model have been studied. In this paper we consider the restriction where all the gates are $α$-imbalanced that is, at most one input of each gate depends on more than $n^α$ variables (where $n$ is the number if variables of the function being represented). The concept of imbalanced gates has been first considered in [Lai, Liu, Yin 'New canonical representations by augmenting OBDDs with conjunctive decomposition', JAIR, 2017]. We consider the idea in the context of representation of \textsc{cnf}s of bounded primal treewidth. We pose an open question as to whether \textsc{cnf}s of bounded primal treewidth can be represented as \textsc{fpt}-sized \textsc{dnnf} with $α$-imbalanced gates. We answer the question negatively for Decision \textsc{dnnf} with $α$-imbalanced conjunction gates. In particular, we establish a lower bound of $n^{Ω((1-α) \cdot k)}$ for the representation size (where $k$ is the primal treewidth of the input \textsc{cnf}). The main engine for the above lower bound is a combinatorial result that may be of an independent interest in the area of parameterized complexity as it introduces a novel concept of bidimensionality. |
| title | Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2505.16012 |