2019/12/17 by Janosch Döcker, Döcker, Janosch
Computer Science · #Advanced Algebra and Logic #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Methods in Verification #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1912.08032
openalex publication_date 2019/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that Monotone 3-Sat remains NP-complete if (i) each clause contains exactly three distinct variables, (ii) each clause is unique, i.e., there are no duplicates of the same clause, and (iii), amongst the clauses, each variable appears unnegated exactly twice and negated exactly twice. Darmann and Döcker [6] recently showed that this variant of Monotone 3-Sat is either trivial or NP-complete. In the first part of the paper, we construct an unsatisfiable instance which answers one of their open questions (Challenge 1) and places the problem in the latter category. Then, we adapt gadgets used in the construction to (1) sketch two reductions that establish NP-completeness in a more direct way, and (2), to show that ∀∃ 3-SAT remains Π2P-complete for quantified Boolean formulas with the following properties: (a) each clause is monotone (i.e., no clause contains an unnegated and a negated variable) and contains exactly three distinct variables, (b) each universal variable appears exactly once unnegated and exactly once negated, (c) each existential variable appears exactly twice unnegated and exactly twice negated, and (d) the number of universal and existential variables is equal. Furthermore, we show that the variant where (b) is replaced with (b') each universal variable appears exactly twice unnegated and exactly twice negated, and where (a), (c) and (d) are unchanged, is Π2P-complete as well. Thereby, we improve upon two recent results by Döcker et al. [8] that establish Π2P-completeness of these variants in the non-monotone setting. We also discuss a special case of Monotone 3-Sat-(2,2) that corresponds to a variant of Not-All-Equal Sat, and we show that all such instances are satisfiable.