Lower bounds are not easier over the reals: inside PH

Hervé Fournier (1) , Pascal Koiran (1)

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

We prove that all NP problems over the reals with addition and order can be solved in polynomial time with the help of a boolean NP oracle. As a consequence, the ``P = NP?'' question over the reals with addition and order is equivalent to the classical question. For the reals with addition and equality only, the situation is quite different since P is known to be different from NP. Nevertheless, we prove similar transfer theorems for the polynomial hierarchy.

On montre que tous les problèmes NP sur les réels avec addition et ordre peuvent êetre résolus en temps polynomial à l'aide d'un oracle NP booléen. Il en résulte que la question ``P=NP ?'' sur les réels avec addition et ordre est équivalente à la question classique. Pour les réels avec addition et égalité la situation est bien différente puisqu'il est connu que P est différent de NP. Cependant, nous démontrons des résultats de transferts similaires pour la hiérarchie polynomiale.

Mots clés: Algebraic Complexity; Blum-Shub-Smale Model; Decision Trees; Point Location; Transfer Theorems

Mots clés: Arbres de Decision; Complexité Algébrique; Localisation de Point; Modèle de Blum-Shub-Smale; Théorèmes de Transfert

Domaines: Informatique [cs]

Hervé Fournier, Pascal Koiran. Lower bounds are not easier over the reals: inside PH. [Research Report] LIP RR-1999-21, Laboratoire de l'informatique du parallélisme. 1999, 2+p. ⟨hal-02102035⟩