# Show that (2,3)-satisfability is np-complete

First of all, I introduce (2,3)-satisfability:
Formulas are in CNF form, the special property is that each clause has $2$ or $3$ literals. Formula is satisfied iff only and only if there exists valuation such that:

• clauses with two literals are treated normally - it sufficient to satisfy one literal (also $2$ literals can be satisfied).
• clauses with three literals are treated specially - there are must be satisfied exactly $2/3$ of literals (no more, no less)

Show that checking if such formula is (2,3)-satisfable is np-complete.
I have no idea how to do it. Obviously, it is easy to show that it is in np, but hardness doesn't seem that easy to show.

1-in-3-SAT is NP Complete: given a set of clauses, find a value assignment such that exactly 1 literal in each clause is made true (http://cs.nyu.edu/courses/fall14/CSCI-UA.0310-001/1in3sat.pdf).

Reduction from 1-in-3-SAT: negate every literal in every clause of the 1-in-3-sat instance. Now exactly two literals need to be made true in each clause instead of one to have an equivalent solution set. This is your (2,3)-satisfiabililty instance. We don't even need the clauses with two literals.

Example

1-in-3-SAT instance: (a,-b,c), (a, b, -c), (d, e, f)
equivalent (2,3)-satisfiability instance: (-a,b,-c), (-a, -b, c), (-d, -e, -f)

• Ok, I give up. What about two clauses. It is not obvious that we can avoid it. I read proof of theorem which you referenced - it also avoids it. – Haskell Fun Jul 29 '17 at 21:42
• Ahh, ok I understand. Simply, we reduce 1-in-3SAT to our problem. Because 1-in-3SAT has not 2-clauses on the whole (it has only 3-claueses) we can forget about two clauses and think that in our task we have only 3-clauses. Yeah ? – Haskell Fun Jul 29 '17 at 22:08

Please note that $$(x_1 \vee x_2 \vee x_3) \text{ is satisfable in 'normal sense' iff } \\ (x_1 \vee x_4 \vee x_5) \wedge (x_2 \vee x_6 \vee x_7) \wedge (x_3 \vee x_8 \vee x_9)\\ \wedge (x_5 \vee x_7 \vee x_9) \\ \text{is 2-satisfable}$$ where are $x_4, x_5, x_6, x_6, x_8, x_9$ are variables that doesn't occur in a formula (they are just new variables).

• There must be easier reduction. For example, 1-in-3 SAT clause can be reduced to 3 2-clauses and 1 3-clause with no new variables involved. – rus9384 Aug 12 '17 at 22:29
• But, do you thnik that reduction works? – Carol Aug 12 '17 at 22:29
• I mean: do you thnik that reduction presented by me in my post works? – Carol Aug 12 '17 at 22:32
• This should work: assuming that original formula is UNSAT, $x_1, x_2, x_3$ are impossible. So, we must use $x_4...x_9$ but then last clause is not 2-satisfied. However, allowing any of $x_1, x_2, x_3$ be presented there, formula becomes 2-satisfiable. – rus9384 Aug 12 '17 at 22:41