4 papers · 1 filter
On simplified NP-complete variants of Not-All-Equal 3-Sat and 3-Sat
Andreas Darmann, Janosch Döcker
We consider simplified, monotone versions of Not-All-Equal 3-Sat and 3-Sat, variants of the famous Satisfiability Problem where each clause is made up of exactly three distinct lit…
Placing quantified variants of 3-SAT and Not-All-Equal 3-SAT in the polynomial hierarchy
Janosch Döcker, Britta Dorn, Simone Linz +1
The complexity of variants of 3-SAT and Not-All-Equal 3-SAT is well studied. However, in contrast, very little is known about the complexity of the problems' quantified counterpart…
On planar variants of the monotone satisfiability problem with bounded variable appearances
Andreas Darmann, Janosch Döcker, Britta Dorn
We show NP-completeness for several planar variants of the monotone satisfiability problem with bounded variable appearances. With one exception the presented variants have an asso…
Monotone 3-Sat-4 is NP-complete
Andreas Darmann, Janosch Döcker
Monotone 3-Sat-4 is a variant of the satisfiability problem for boolean formulae in conjunctive normal form. In this variant, each clause contains exactly three literals---either a…