# What can be solved with semidefinite programming that can't be solved with linear programming?

I'm familiar with linear programs in that they can solve problems with linear objective functions and linear constraints. But what can semidefinite programming solve that linear programming can't? I already know that semidefinite programs are a generalization of linear programs.

Also, how does one recognize a problem that can be solved using semidefinite programming? What is a typical problem that semidefinite programming is used for that couldn't be solved via linear programming?

Thanks very much for any response.

• Maybe you can make your question more precise? After all, linear programming is $\mathsf{P}$-complete. – Kristoffer Arnsfelt Hansen Dec 11 '13 at 12:40
• @KristofferArnsfeltHansen I never stop wondering why people keep bringing this fact up in similar discussions. P-completeness is irrelevant unless we are talking about separating P from L or NC - if we are talking about polytime, everything in P is "P-complete". To suggest an answer to OP: once you fix a linear encoding of a problem, (i.e. write as optimizing a linear functional over a polytope) it makes perfect sense to ask whether a polysize LP/SDP can solve the problem. – Sasho Nikolov Dec 11 '13 at 15:57