Lower bounds are not easier over the reals: inside PH
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.
Origine | Fichiers produits par l'(les) auteur(s) |
---|