Difficulté du résultant et des grands déterminants

Résumé : Le résultant est un polynôme permettant de déterminer si plusieurs polynômes donnés ont une racine commune. Canny a pu donner un algorithme PSPACE calculant le résultant à l'aide de calculs de déterminants, mais pose la question de sa complexité exacte. On s'intéresse ici à donner une estimation plus fine de cette complexité. D'une part, on montre que le résultant est dans AM, et qu'il est NP-difficile sous réduction probabiliste. D'autre part, les matrices en jeu étant descriptibles par des circuits de taille raisonnable, on montre que le calcul du déterminant pour de telles matrices est PSPACE-complet.
Document type :
Reports
Complete list of metadatas

Cited literature [41 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00431714
Contributor : Bruno Grenet <>
Submitted on : Friday, November 13, 2009 - 2:17:42 AM
Last modification on : Tuesday, April 24, 2018 - 1:52:30 PM
Long-term archiving on : Tuesday, October 16, 2012 - 1:55:42 PM

File

rapp-rech.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial - ShareAlike 4.0 International License

Identifiers

  • HAL Id : ensl-00431714, version 1

Collections

Citation

Bruno Grenet. Difficulté du résultant et des grands déterminants. [Rapport de recherche] RRLIP2009-32, Laboratoire de l'Informatique du Parallélisme. 2009. ⟨ensl-00431714⟩

Share

Metrics

Record views

150

Files downloads

179