2
$\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)?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
9
$\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.

Improve this answer
$\endgroup$
8
  • $\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
    Commented Jul 26, 2017 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
    Commented Jul 26, 2017 at 19:55
  • $\begingroup$ Well, you have to keep thinking. $\endgroup$
    – Yuval Filmus
    Commented Jul 26, 2017 at 20:47
  • $\begingroup$ What do you mean? $\endgroup$
    – Carol
    Commented Jul 26, 2017 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
    Commented Jul 26, 2017 at 20:59

Your Answer

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

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