Abstract:
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 do so, we compare these problems with the Graph Isomorphism problem. Moreover, using Interactive Proofs \cite{zk} we prove that, provided the Polynomial Hierarchy does not collapse, these problems are not NP-Complete (resp. NP-Hard).