$3EQ \leq _P 2EQ$

Question

Let:

• $2EQ$ - The language of all binary ($\mathbb{Z}_2$) equation sets that have a solution in $\mathbb{Z}_2$, where each multiplication is of at most two $x_i,\, x_j$. Meaning a set of equations of the form: $\Sigma a_i \cdot x_i + \Sigma \, \Sigma \, a_{i,j} \cdot x_i \cdot x_j = b $.
• $3EQ$ - Same just up to at most 3 multiplications, meaning a set of equations of the form: $\Sigma a_i \cdot x_i + \Sigma \, \Sigma \, a_{i,j} \cdot x_i \cdot x_j + \Sigma \, \Sigma \, \Sigma \, a_{i,j,k} \cdot x_i \cdot x_j \cdot x_k = b $.

I'd like to show that $3EQ \leq _P 2EQ$, but I don't know how to deal with the expressions of $x_i \cdot x_j \cdot x_k$. I thought about trying to represent them with using only at most two $\wedge$'s, but not sure if it's even possible. Maybe there's a better idea?

Answer 1

Hint: You can add a variable $x_{ij}$ whose value is always $x_ix_j$ by adding the equation $x_{ij}-x_ix_j=0$. This allows you to reduce cubic equations to quadratic ones.

Answer 2

They're both NP-hard, and both in NP, so they are both NP-complete. Therefore, there is a reduction between them.

Hint: Try proving that Independent SET $\le_P$ 2EQ. Once you prove that, you should be able to take it from there, as the desired result follows immediately.