Transfer theorems via sign conditions

Pascal Koiran (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

We show that P = PSPACE implies the collapse of the boolean polynomial hierarchy over any structure which admits ``efficient enumeration of sign conditions''. This fairly rich class of structures contains in particular R and C.

Nous montrons que si P = PSPACE la hiérarchie polynomiale booléenne s'effondre pour toute structure vérifiant la propriétée d'énumération efficace des conditions de signes. Cette classe de structures assez riche contient en particulier R et C.

Mots clés: Algebraic Complexity; Polynomial Hierarchy; Sign Conditions; Transfer Theorems

Mots clés: Complexité Algébrique; Conditions de Signe; Hiérarchie Polynomiale; Théorèmes de Transfert

Domaines: Informatique [cs]

Pascal Koiran. Transfer theorems via sign conditions. [Research Report] LIP RR-2000-13, Laboratoire de l'informatique du parallélisme. 2000, 2+7p. ⟨hal-02101937⟩