ECCC-Report TR04-116https://eccc.weizmann.ac.il/report/2004/116Comments and Revisions published for TR04-116en-usSat, 11 Dec 2004 18:05:54 +0200
Paper TR04-116
| On the computational complexity of some equivalence problems of polynomial systems of equations over finite fields |
PERRET ludovic
https://eccc.weizmann.ac.il/report/2004/116We 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).
Sat, 11 Dec 2004 18:05:54 +0200https://eccc.weizmann.ac.il/report/2004/116