Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Reports

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 metadata

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

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

7

Files downloads

85