Complexity of solving system of binary quadratic equations modulo $3$

Question

What is the complexity of solving system of binary quadratic equations modulo $3$?

$f_i(x_i,x_j)=0 \bmod 3, \deg{f_i}=2$.

Modulo $2$ can be formulated as 2-SAT, so it is polynomial in the number of variables.

One way to answer is to show it is NP-hard.

Daniel Weber · Accepted Answer · 2024-08-13 12:56:20Z

3

Note that $(x-y-1)(x-y-2) = 0 \leftrightarrow x \neq y$, so this is NP-complete (even with all $f_i$ equal to that) by a reduction from 3-Coloring.

answered Aug 13 at 12:56

Daniel Weber

3,3191 gold badge12 silver badges26 bronze badges

$\begingroup$ Indeed, many thanks. $\endgroup$
– joro
Commented Aug 13 at 13:58
$\begingroup$ This also answers the first linked question, so I will accept it as answer there too. $\endgroup$
– joro
Commented Aug 13 at 14:32
1

$\begingroup$ There is stronger result: every variable occurs bounded number of times, coming from coloring bounded degree graphs. $\endgroup$
– joro
Commented Aug 14 at 5:25

Add a comment |

1 Answer 1