We study in this paper the computational complexity of some equivalence relations on polynomial systems of equations over finite fields. These problems are analyzed with respect to polynomial-time many-one reductions (resp. Turing reductions, Levin reductions). In particular, we show that some of these problems are between P and NP. To ... more >>>