# Satisfiability of at least k linear equations over Z2 is NP-hard

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

• Make sure that when the clause is not satisfied, fewer than that constant number of equations are satisfied. ​ ​
– user12859
May 6, 2017 at 22:02
• 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? May 7, 2017 at 4:41
• 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. ​ ​ ​ ​
– user12859
May 7, 2017 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.