2016/04/22 by Mengel, Stefan
#Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1604.06715
We show unconditional parameterized lower bounds in the area of knowledge compilation, more specifically on the size of circuits in decomposable negation normal form (DNNF) that encode CNF-formulas restricted by several graph width measures. In particular, we show that - there are CNF formulas of size n and modular incidence treewidth k whose smallest DNNF-encoding has size nΩ(k), and - there are CNF formulas of size n and incidence neighborhood diversity k whose smallest DNNF-encoding has size nΩ(√(k)). These results complement recent upper bounds for compiling CNF into DNNF and strengthen---quantitatively and qualitatively---known conditional low\-er bounds for cliquewidth. Moreover, they show that, unlike for many graph problems, the parameters considered here behave significantly differently from treewidth.