pith. sign in

arxiv: 1708.07767 · v1 · pith:JKIUM47Cnew · submitted 2017-08-25 · 💻 cs.AI · cs.CC

Non-FPT lower bounds for structural restrictions of decision DNNF

classification 💻 cs.AI cs.CC
keywords treewidthboundeddecisiondnnfincidenceknowledgelowermodels
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.