1 citations · 2 across the 2 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2019
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…
cs.CC2016
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…
cs.CC2016
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…