On simplified NP-complete variants of Not-All-Equal 3-Sat and 3-Sat
share
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 literals. We show that Not-All-Equal 3-Sat remains NP-complete even if (1) each variable appears exactly four times, (2) there are no negations in the formula, and (3) the formula is linear, i.e., each pair of distinct clauses shares at most one variable. Concerning 3-Sat we prove several hardness results for monotone formulas with respect to a variety of restrictions imposed on the variable appearances. Monotone 3-Sat is the restriction of 3-Sat to monotone formulas, i.e. to formulas in which each clause contains only unnegated variables or only negated variables, respectively. In particular, we show that, for any k≥ 5, Monotone 3-Sat is NP-complete even if each variable appears exactly k times unnegated and exactly once negated. In addition, we show that Monotone 3-Sat is NP-complete even if each variable appears exactly three times unnegated and three times negated, respectively. In fact, we provide a complete analysis of Monotone 3-Sat with exactly six appearances per variable. Further, we prove that the problem remains NP-complete when restricted to instances in which each variable appears either exactly once unnegated and three times negated or the other way around. Thereby, we improve on a result by Darmann et al. [DDD18] showing NP-completeness for four appearances per variable. Our stronger result also implies that 3-Sat remains NP-complete even if each variable appears exactly three times unnegated and once negated, therewith complementing a result by Berman et al. [BKS03].
READ FULL TEXT