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.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02102035
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:12:32 AM
Last modification on : Sunday, April 28, 2019 - 1:23:10 AM

File

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

Identifiers

  • HAL Id : hal-02102035, version 1

Collections

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⟩

Share

Metrics

Record views

11

Files downloads

21