Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR04-116 | 18th November 2004 00:00

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

TR04-116
Authors: PERRET ludovic
Publication: 11th December 2004 18:05
Keywords:

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

ISSN 1433-8092 | Imprint