1
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ Make sure that when the clause is not satisfied, fewer than that constant number of equations are satisfied. ​ ​ $\endgroup$
    – user12859
    May 6, 2017 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$
    – user1767774
    May 7, 2017 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, 2017 at 16:16

1 Answer 1

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for the response. Sorry for my ignorance, but what does ⊕ mean? $\endgroup$
    – user1767774
    May 7, 2017 at 19:37
  • $\begingroup$ It stands for XOR. $\endgroup$
    – Yuval Filmus
    May 7, 2017 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$
    – user1767774
    May 7, 2017 at 19:54
  • $\begingroup$ Yes, that's the idea. $\endgroup$
    – Yuval Filmus
    May 7, 2017 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$
    – Yuval Filmus
    May 7, 2017 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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