The multivariate resultant lies between NP and AM

Rapport de Recherche RRLIP2009-34 The resultant of a square system of homogeneous polynomials is a polynomial in their coefficients which vanishes whenever the system has a solution. Canny gave an algorithm running in polynomial space to compute it but no lower bound was known. We investigate the complexity of the associated decision problem and give a hardness result: Testing the resultant for zero lies in the class Arthur −Merlin and is NP-hard. We give a randomized reduction and a deterministic reduction for NP-hardness. The latter can be seen as a derandomization result