# zbMATH — the first resource for mathematics

On the complexity of semidefinite programs. (English) Zbl 0881.90127
Summary: We show that the feasibility of a system of $$m$$ linear inequalities over the cone of symmetric positive semidefinite matrices of order $$n$$ can be tested in $$mn^{O(\min\{m,n^2\})}$$ arithmetic operations with $$ln^{O(\min\{m,n^2\})}$$-bit numbers, where $$l$$ is the maximum binary size of the input coefficients. We also show that any feasible system of dimension $$(m,n)$$ has a solution $${\mathbf X}$$ such that $$\log|{\mathbf X}|\leq ln^{O(\min\{m,n^2\})}$$.

##### MSC:
 90C60 Abstract computational complexity for mathematical programming problems
Full Text: