Bollig, BeateFarenholtz, Martin2021-03-122021-03-122020-08-17http://hdl.handle.net/2003/40080http://dx.doi.org/10.17877/DE290R-21957Structured d-DNNFs and SDDs are restricted negation normal form circuits used in knowledge compilation as target languages into which propositional theories are compiled. Structuredness is imposed by so-called vtrees. By definition SDDs are restricted structured d-DNNFs. Beame and Liew (2015) as well as Bova and Szeider (2017) mentioned the question whether structured d-DNNFs are really more general than SDDs w.r.t. polynomial-size representations (w.r.t. the number of Boolean variables the represented functions are defined on.) The main result in the paper is the proof that a function can be represented by SDDs of polynomial size if the function and its complement have polynomial-size structured d-DNNFs that respect the same vtree.enComplexity theoryDecomposable negation normal formsKnowledge compilationSentential decision diagrams004TextKomplexitätstheorieNormalformEntscheidungsgraph