Non-FPT lower bounds for structural restrictions of decision DNNF
This provides the first parameterized separation for knowledge compilation, addressing a theoretical gap in computational complexity for researchers in AI and logic.
The paper tackled the problem of separating primal treewidth and incidence treewidth for knowledge compilation models, showing that structured decision DNNF and OBDD have non-FPT size lower bounds for CNF-formulas of bounded incidence treewidth, while they are known to be FPT size for bounded primal treewidth.
We give a non-FPT lower bound on the size of structured decision DNNF and OBDD with decomposable AND-nodes representing CNF-formulas of bounded incidence treewidth. Both models are known to be of FPT size for CNFs of bounded primal treewidth. To the best of our knowledge this is the first parameterized separation of primal treewidth and incidence treewidth for knowledge compilation models.