# Lower bounds are not easier over the reals: inside PH

Abstract : 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.
Keywords :
Document type :
Reports
Domain :

https://hal-lara.archives-ouvertes.fr/hal-02102035
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:12:32 AM
Last modification on : Saturday, September 11, 2021 - 3:19:16 AM

### File

RR1999-21.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-02102035, version 1

### Citation

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⟩

### Metrics

Les métriques sont temporairement indisponibles