4
$\begingroup$

Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs.

Is there a survey/lecture notes describing generalizations of LP that can be solved in poly time?

This is related to this question, but the questions in that post are quite different and most of the questions have not been answered.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ I think the general rule is: (1) convex optimization problems are polynomially solvable, and (2) as soon as non-convexity pops up you hit NP-hardness. $\endgroup$
    – Gamow
    Feb 26, 2019 at 18:19
  • 2
    $\begingroup$ I think that is a good rule of thumb, however, there are polynomial time solvable nonconvex programs and NP-hard convex problems $\endgroup$
    – user2316602
    Feb 27, 2019 at 13:17

1 Answer 1

Reset to default
10
$\begingroup$

Fixed Point Logic $+$ Counting (FPC) is believed to capture most of the $P$ solvable problems. Anderson, Dawar and Holm 2015 [1]showed that optimization of linear programs is expressible in FPC. Dawar and Wang 2016 [2]showed that The FPC implementation of the ellipsoid method extends to semidefinite programs (subject to some technical conditions).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Great answer! How big is the constant in the $O$? I wouldn't be surprised by something astronomical as in Courcelle's theorem. Is the algorithm practical? Is it known (as in the case of Courcelle's theorem) that the constant has to be huge when parametrised by the length of the formula? $\endgroup$
    – user2316602
    Feb 27, 2019 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.