Elimination of parameters in the polynomial hierarchy - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1998

Elimination of parameters in the polynomial hierarchy

(1)
1

Résumé

Blum, Cucker, Shub and Smale have shown that the problem ``$\p = \np$~?'' has the same answer in all algebraically closed fields of characteristic~0. We generalize this result to the polynomial hierarchy: if it collapses over an algebraically closed field of characteristic 0, then it must collapse at the same level over all algebraically closed fields of characteristic 0. The main ingredient of their proof was a theorem on the elimination of parameters, which we also extend to the polynomial hierarchy. Similar but somewhat weaker results hold in positive characteristic. The present paper updates a report (LIP Research Report 97-37) with the same title, and in particular includes new results on interactive protocols and boolean parts.
Blum, Cucker, Shub et Smale ont montré que la réponse au problème ``$\p = \np$~?'' est la même dans tous les corps algébriquement clos de caractéristique 0. Nous généralisons ce résultat à la hiérarchie polynomiale: si elle s'effondre pour un corps algébriquement clos de caractéristique 0, alors elle s'effondre au même niveau pour tous les corps algébriquement clos de caractéristique 0. L'ingrédient principal de leur démonstration est un théorème d'élimination des paramètres, que nous étendons également à la hiérarchie polynomiale. Des résultats similaires mais un peu plus faibles s'appliquent en caractéristique positive. Cet article met à jour un rapport précédent (rapport de recherche LIP 97-37) portant le même titre, et contient notamment des résultats nouveaux sur les preuves interactives et les parties booléennes.
Fichier principal
Vignette du fichier
RR1998-15.pdf (247.78 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101807 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101807 , version 1

Citer

Pascal Koiran. Elimination of parameters in the polynomial hierarchy. [Research Report] LIP RR-1998-15, Laboratoire de l'informatique du parallélisme. 1998, 2+18p. ⟨hal-02101807⟩
8 Consultations
67 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More