Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

Elimination of parameters in the polynomial hierarchy

Abstract : 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.
Document type :
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:06:49 AM
Last modification on : Saturday, September 11, 2021 - 3:19:19 AM


Files produced by the author(s)


  • HAL Id : hal-02101807, version 1



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⟩



Record views


Files downloads