Given a system of $m$ equations in $n$ boolean variables:

$$\begin{align} a_{11}x_1 + a_{12}x_2 + \dots +a_{1n}x_n &= b_1\pmod2\\ a_{21}x_1 + a_{22}x_2 + \dots +a_{2n}x_n &= b_2\pmod2\\ &\;\vdots\\ a_{m1}{x_1} + a_{m2}x_2 + \dots +a_{mn}x_n &= b_m\pmod2 \end{align}$$

Where all $a_{ij}, x_i$ and $b_i$ are $0$ or $1$, I want to prove that the decision problem of finding if there is a vector $x$ that satisfies at least $k$ equation, is NP hard.

I was given a hint to reduce from 3-SAT, so I am trying to build from each clause in the 3-SAT formula several equations, such that a constant number of them is satisfied iff the clause is satisfied. But I am not sure how to impose this restriction of a constant number of equations satisfied (for all different truth assignments that satisfy the given clause).

  • $\begingroup$ Make sure that when the clause is not satisfied, fewer than that constant number of equations are satisfied. ​ ​ $\endgroup$
    – user12859
    May 6 '17 at 22:02
  • $\begingroup$ But I am trying to prevent a situation where k equations are sastified, but none of them represents the satisfaction of a specific clause, hence the entire boolean formula is actually not satisfied. As far as I understand, to ensure that I must make sure that a constant number of equations is satisfied iff the clause is satisfied, not "more than k for some k". Am I wrong? $\endgroup$ May 7 '17 at 4:41
  • $\begingroup$ I apparently mis-interpreted your question ​ - ​ I thought what you weren't sure about was why a gadget with specified properties sufficed, rather than how to get such a gadget. ​ ​ ​ ​ $\endgroup$
    – user12859
    May 7 '17 at 16:16

Consider any clause $x \lor y \lor z$, and the following table: $$ \begin{array}{c|c|c|c} \text{satisfied literals} & [x]+[y]+[z] & [x\oplus y] + [x\oplus z] + [y\oplus z] & [x\oplus y\oplus z] \\\hline 0 & 0 & 0 & 0 \\\hline 1 & 1 & 2 & 1 \\\hline 2 & 2 & 2 & 0 \\\hline 3 & 3 & 0 & 1 \end{array} $$ Here $[x]$ is 1 if $x$ is satisfied and 0 otherwise.

The first row sums to 0, and the rest sum to 4 (ignoring the column labeled "satisfied literals"). Can you use this to your advantage?

  • $\begingroup$ Thanks for the response. Sorry for my ignorance, but what does ⊕ mean? $\endgroup$ May 7 '17 at 19:37
  • $\begingroup$ It stands for XOR. $\endgroup$ May 7 '17 at 19:37
  • $\begingroup$ I think I understand;is it right to say that [x]+[y]+[z] corresponds to the three equations 1*x = 1, 1*y=1, 1*z=1, and [x⊕z] (for example) corresponds to 1*x + 0*y + 1*z = 1? $\endgroup$ May 7 '17 at 19:54
  • $\begingroup$ Yes, that's the idea. $\endgroup$ May 7 '17 at 19:57
  • 1
    $\begingroup$ I might have seen this gadget before, or at least something similar. The more you practice, the easier it will be to come up with these reductions. $\endgroup$ May 7 '17 at 19:59

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.