__
TR04-116 | 18th November 2004 00:00
__

#### On the computational complexity of some equivalence problems of polynomial systems of equations over finite fields

**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).