14 citations · 26 across the 14 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.AI2017★ 3 cited
Non-FPT lower bounds for structural restrictions of decision DNNF
Andrea Calì, Florent Capelli, Igor Razgon
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…
cs.CC2017★ 2 cited
On The Complexity of Enumeration
Florent Capelli, Yann Strozecki
We investigate the relationship between several enumeration complexity classes and focus in particular on problems having enumeration algorithms with incremental and polynomial del…
cs.CC2017
Understanding the complexity of #SAT using knowledge compilation
Florent Capelli
Two main techniques have been used so far to solve the #P-hard problem #SAT. The first one, used in practice, is based on an extension of DPLL for model counting called exhaustive…