2025/05/21 by Igor Razgon, Razgon, Igor
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2505.16012
Decomposable Negation Normal Forms dnnf [Darwiche, 'Decomposable Negation Normal Form', JACM, 2001] is a landmark Knowledge Compilation (kc) model, highly important both in 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 cnfs of bounded primal treewidth. We pose an open question as to whether cnfs of bounded primal treewidth can be represented as fpt-sized dnnf with α-imbalanced gates. We answer the question negatively for Decision dnnf with α-imbalanced conjunction gates. In particular, we establish a lower bound of nΩ((1-α) ⋅ k) for the representation size (where k is the primal treewidth of the input 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.