Efficient Explanations for Knowledge Compilation Languages
  Knowledge compilation (KC) languages find a growing number of practical uses,
including in Constraint Programming (CP) and in Machine Learning (ML). In most
applications, one natural question is how to explain the decisions made by
models represented by a KC language. This paper shows that for many of the best
known KC languages, well-known classes of explanations can be computed in
polynomial time. These classes include deterministic decomposable negation
normal form (d-DNNF), and so any KC language that is strictly less succinct
than d-DNNF. Furthermore, the paper also investigates the conditions under
which polynomial time computation of explanations can be extended to KC
languages more succinct than d-DNNF.
