pith. sign in

arxiv: 1603.07881 · v1 · pith:UWR73ONEnew · submitted 2016-03-25 · 💻 cs.CC

Monotone 3-Sat-4 is NP-complete

classification 💻 cs.CC
keywords clausemonotonesat-4containseverynp-completepositivethree
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.