Timeline for Deciding whether a convex region is empty
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 19, 2023 at 16:27 | comment | added | Neal Young | @EmilJeřábek, okay, that makes sense. (I was considering OP's question to be the general one, without the assumption that the functions are polynomials.) | |
| Dec 18, 2023 at 14:26 | comment | added | Emil Jeřábek | @NealYoung I don’t even need that they are convex. I only need that they are polynomials with rational (or: real algebraic, if represented in a suitable way) coefficients, as I wrote above. | |
| Dec 18, 2023 at 14:08 | comment | added | Neal Young | @EmilJeřábek, for that to work don't you need to assume something about the $g_i$'s (beyond the given assumption that they are convex)? | |
| Dec 18, 2023 at 13:47 | comment | added | Tassle | @ErelSegal-Halevi The quoted passage doesn't focus on polynomials, does it? The existential theory of the reals does, so this might be were the disconnect lies. Also it says "in practice". I don't think that a PSPACE algorithm is very practical, in general. | |
| Dec 17, 2023 at 18:01 | comment | added | Erel Segal-Halevi | I am surprised that the problem can be decided in finite time, since the passage I quoted from the book on convex optimization apparently shows that the run-time might be infinite. Or maybe I did not understand it correctly? | |
| Dec 17, 2023 at 15:51 | comment | added | Emil Jeřábek | For this direction, the trivial reduction works: $\exists\vec x\,\bigwedge_ig_i(\vec x)\le0$ is, literally, an existential statement in the theory of the reals. | |
| Dec 17, 2023 at 13:36 | comment | added | Neal Young | @EmilJeřábek,perhaps, but I don't think the reduction described in the answer shows that (except in the easy case when the given polynomials are linear). | |
| Dec 16, 2023 at 19:37 | comment | added | Emil Jeřábek | @NealYoung The case of “polynomials with rational coefficients” in the OP’s question is solvable in $\exists\mathbb R\subseteq \mathrm{PSPACE}$. | |
| Dec 16, 2023 at 14:34 | comment | added | Neal Young | When you say "the problem still lies in PSPACE", which problem do you mean? It seems like you mean the problem you discuss in your answer. But the problem in OP's post doesn't (in general) reduce to the problem you discuss in your answer, so I don't think you can conclude that OP's problem is in PSPACE. | |
| Dec 15, 2023 at 18:18 | history | edited | user67422 | CC BY-SA 4.0 |
added 221 characters in body
|
| Dec 15, 2023 at 16:38 | comment | added | Neal Young | Wait a minute, the sum of squares is not necessarily convex in $x$. Eg. consider $[(1-x)(1+x)]^2$ (here's a plot) | |
| Dec 15, 2023 at 12:27 | vote | accept | Erel Segal-Halevi | ||
| Dec 16, 2023 at 17:46 | |||||
| Dec 15, 2023 at 7:46 | comment | added | Emil Jeřábek | @ErelSegal-Halevi The original algorithm is due to Canny, Some algebraic and geometric computations in PSPACE, doi.org/10.1145/62212.62257 . A follow-up improvement: doi.org/10.1093/comjnl/36.5.409 | |
| Dec 15, 2023 at 6:02 | comment | added | Chandra Chekuri | A simple Google search gives this useful description on Wikipedia. en.wikipedia.org/wiki/Existential_theory_of_the_reals | |
| Dec 14, 2023 at 21:51 | comment | added | Erel Segal-Halevi | Does it mean that it is in PSPACE? So it can be solved in exponential time? By what algorithm? | |
| Dec 14, 2023 at 20:13 | history | undeleted | user67422 | ||
| Dec 14, 2023 at 20:13 | history | edited | user67422 | CC BY-SA 4.0 |
added 467 characters in body
|
| Dec 14, 2023 at 19:31 | history | deleted | user67422 | via Vote | |
| Dec 14, 2023 at 19:30 | history | answered | user67422 | CC BY-SA 4.0 |