Linear Programming corresponds to first order theory of reals with addition and order. What theory do notions such as semidefinite programming, second order cone programming and convex programming correspond to? (I am interested in quantified statements in addition to $\exists\forall$ statements).
$\begingroup$
$\endgroup$
8
-
4$\begingroup$ You'll have to explain more clearly what you mean by "corresponds to". Should the answer be a first-order theory? Certainly there are first-order languages on the reals which are capable of expressing these kinds of programming problems, but it sounds like you're hoping for a tighter connection... can you make this more precise? $\endgroup$– Alex KruckmanAug 4, 2020 at 18:25
-
$\begingroup$ I am just looking for general framework to view these. And a more precise connection. If I know how to express my thoughts properly I would not be posting this. Sorry. It is unclear to me but I think there is something more deeper. $\endgroup$– VS.Aug 4, 2020 at 18:34
-
$\begingroup$ I'm torn between finding that this question needs details or clarity, and so joining the close voters, and finding it interesting even in its current incompetely posed form. I think MO has historically demonstrated tolerance for interesting "first give the right form of the question, and then answer it" questions of this type, so I came down on the side of upvoting—because I'd rather see if somebody can give an interesting answer to this question than keep MO formally tidy by removing it. $\endgroup$– LSpiceAug 4, 2020 at 19:32
-
3$\begingroup$ I've simultaneously upvoted and voted to close as unclear; I think there's probably a very good question lurking here, and so I want to encourage it, but at present I don't think it admits a reasonable answer. $\endgroup$– Noah SchweberAug 4, 2020 at 19:54
-
$\begingroup$ “Linear programming is equivalent to an algorithm for deciding and witnessing $\exists\forall$ statements in the language $(+,<)$. Are there languages for which the corresponding algorithms are equivalent to semi-definite, second-order cone or convex programming?” $\endgroup$– user44143Aug 6, 2020 at 8:48
|
Show 3 more comments