Lower bounds are not easier over the reals: inside PH - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1999

Lower bounds are not easier over the reals: inside PH

(1) , (1)
1

Résumé

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.
Fichier principal
Vignette du fichier
RR1999-21.pdf (320.19 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : hal-02102035 , version 1

Citer

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⟩
10 Consultations
96 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More