1
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Carol Jul 26 '17 at 19:23
  • $\begingroup$ Showing that it is NP is easy: Just nondeterministically guess every possible valuation and check whether is it solution. it (in polynomial time). $\endgroup$ – Carol Jul 26 '17 at 19:55
  • $\begingroup$ Well, you have to keep thinking. $\endgroup$ – Yuval Filmus Jul 26 '17 at 20:47
  • $\begingroup$ What do you mean? $\endgroup$ – Carol Jul 26 '17 at 20:58
  • $\begingroup$ You said you don't understand why what I wrote is useful. Others seems to have understood, so I suggest you keep thinking about it. $\endgroup$ – Yuval Filmus Jul 26 '17 at 20: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.