# NP-completeness of solving quadratic equations over $\mathbb{Z}_2$

Let $\chi$ be a degree 2 equation over $\mathbb{Z}_2$ of the form: $$x_{i_1}x_{j_1} + x_{i_{2}}x_{j_1} + \cdots + x_{i_m}x_{j_m} + x_{k_1} + \cdots + x_{k_l} = b$$ for $k_i \in \{1, \dots, n\}, b \in \{0,1\}$ for some $m, l \in \mathbb{N}$

Prove that deciding whether a system of such equations has a solution is NP-complete.

So, we should to prove two things:

1) The problem $\in NP$

2) Another NP-complete problem can be reduced to that problem.

I have no idea how to start. Please hint me. It is tempting to use $SAT$ problem, but, when I am trying to convert that problem I got stuck: How to get $1$ (the truth value)?

You can express the constraint $x \lor y = z$ (where $\lor$ is the OR operator) as the equation $(1-x)(1-y) = (1-z)$, that is, $xy+x+y+z=0$. Using this primitive you can express SAT, showing that your problem is NP-hard. Showing that it is in NP is easier.
• thanks. But, I cannot understand why do you use $z$ in your equation. You have: $xy+x+y+z=0$. $z$ is constant ($0$ or $1$). If you can use constant it is trivial to express $x \vee y$ using xor. But, I don't see that we can use constant. – Carol Jul 26 '17 at 19:23