On complexity of restricted fragments of Decision DNNF

Andrea Calí, Igor Razgon

Decision \textsc{dnnf} (a.k.a. ${\wedge }_d$-\textsc{fbdd}) is an important special case of Decomposable Negation Normal Form (\textsc{dnnf}), a landmark knowledge compilation model.…