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.
Type de document :
Rapport
[Rapport de recherche] RRLIP2009-32, Laboratoire de l'Informatique du Parallélisme. 2009
Liste complète des métadonnées

Littérature citée [41 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00431714
Contributeur : Bruno Grenet <>
Soumis le : vendredi 13 novembre 2009 - 02:17:42
Dernière modification le : mardi 24 avril 2018 - 13:52:30
Document(s) archivé(s) le : mardi 16 octobre 2012 - 13:55:42

Fichier

rapp-rech.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Partage selon les Conditions Initiales 4.0 International License

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

137

Téléchargements de fichiers

128