 |
HAL-LARA Libre accès aux rapports scientifiques et techniques |
 |
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.
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
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)
