2016/03/25 by Darmann, Andreas, Döcker, Janosch
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1603.07881
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 all or none of them are positive, i.e., no clause contains both a positive and a negative literal---and every variable appears at most four times in the formula. Moreover, every clause consists of three distinct literals. We show that Monotone 3-Sat-4 is NP-complete.