1
$\begingroup$

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.

Improve this question
$\endgroup$
0
3
$\begingroup$

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)
Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Haskell Fun Jul 29 '17 at 21:42
  • 1
    $\begingroup$ 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 ? $\endgroup$ – Haskell Fun Jul 29 '17 at 22:08
2
$\begingroup$

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).

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – rus9384 Aug 12 '17 at 22:29
  • $\begingroup$ But, do you thnik that reduction works? $\endgroup$ – Carol Aug 12 '17 at 22:29
  • $\begingroup$ I mean: do you thnik that reduction presented by me in my post works? $\endgroup$ – Carol Aug 12 '17 at 22:32
  • 1
    $\begingroup$ 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. $\endgroup$ – rus9384 Aug 12 '17 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.