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.

  • 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 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 at 13:17

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).

  • $\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 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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