Extensions and Variants of Dalal's Quad Polynomial Fragments of SAT
Balasim Al-Saedi, Éric Grégoire, Bertrand Mazure, Lakhdar Saïs · 2014
An extension and several variants of Dalal's Quad polynomial fragments of SAT are presented. Firstly, the stability of Quad fragments is investigated. Then, the extension is as follows. Quad fixed total orderings of clauses is accompanied with specific additional separate orderings of maximal sub-clauses. Interestingly, the resulting fragments extend Quad without degrading its worst-case complexity. Several other variants of Quad that give rise to additional different polynomial fragments are then investigated.