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.