Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




TR04-116
Authors: PERRET ludovic
Publication: 11th December 2004 18:05
Downloads: 1122
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