ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 4.2. <s> AbstractWe 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 ::: $$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 X such that log||X|| ≤ ::: $$ln^{o(\min \{ m,n^2 \} )} $$ ::: . <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 4.2. <s> In this paper, we present a new and more complete duality for Semidefinite Programming (SDP), with the following features: \begin{itemize} \item This dual is an explicit semidefinite program, whose number of variables and the coefficient bitlengths are polynomial in those of the primal. \item If the Primal is feasible, then it is bounded if and only if the dual is feasible. \item The duality gap, \ie the difference between the primal and the dual objective function values, is zero whenever the primal is feasible and bounded. Also, in this case, the dual attains its optimum \item It yields a precise Farkas Lemma for semidefinite feasibility systems, \ie characterization of the {\it infeasibility} of a semidefinite inequality in terms of the {\it feasibility} of another polynomial size semidefinite inequality. \end{itemize} Note that the standard duality for Linear Programming satisfies all of the above features, but no such duality theory was previously known for SDP, without Slater-like conditions being assumed. Then we apply the dual to derive certain complexity results for Semidefinite Programming Problems. The decision problem of Semidefinite Feasibility (SDFP), \ie that of determining if a given semidefinite inequality system is feasible, is the central problem of interest. The complexity of SDFP is unknown, but we show the following: 1) In the Turing machine model, SDFP is not NP-Complete unless NP=Co-NP; 2) In the real number model of Blum, Shub and Smale\cite{bss}, SDFP is in NP$\cap$Co-NP. We then give polynomial reductions from the following problems to SDFP: 1) Checking whether an SDP is bounded; 2) Checking whether a feasible and bounded SDP attains the optimum; 3) Checking the optimality of a feasible solution. <s> BIB002 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 4.2. <s> 1 Introduction.- 2 Definitions and First Properties of Computation.- 3 Computation over a Ring.- 4 Decision Problems and Complexity over a Ring.- 5 The Class NP and NP-Complete Problems.- 6 Integer Machines.- 7 Algebraic Settings for the Problem "P ? NP?".- 8 Newton's Method.- 9 Fundamental Theorem of Algebra: Complexity Aspects.- 10 Bezout's Theorem.- 11 Condition Numbers and the Loss of Precision of Linear Equations.- 12 The Condition Number for Nonlinear Problems.- 13 The Condition Number in ?(H(d).- 14 Complexity and the Condition Number.- 15 Linear Programming.- 16 Deterministic Lower Bounds.- 17 Probabilistic Machines.- 18 Parallel Computations.- 19 Some Separations of Complexity Classes.- 20 Weak Machines.- 21 Additive Machines.- 22 Nonuniform Complexity Classes.- 23 Descriptive Complexity.- References. <s> BIB003 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 4.2. <s> A rational number can be naturally presented by an arithmetic computation (AC): a sequence of elementary arithmetic operations starting from a fixed constant, say 1. The asymptotic complexity issues of such a representation are studied e.g. in the framework of the algebraic complexity theory over arbitrary field. Here we study a related problem of the complexity of performing arithmetic operations and computing elementary predicates, e.g. ``='' or ``>'', on rational numbers given by AC. In the first place, we prove that AC can be efficiently simulated by the exact semidefinite programming (SDP). Secondly, we give a BPP-algorithm for the equality predicate. Thirdly, we put ``>''-predicate into the complexity class PSPACE. We conjecture that ``>''-predicate is hard to compute. This conjecture, if true, would clarify the complexity status of the exact SDP - a well known open problem in the field of mathematical programming. <s> BIB004
Complexity of semi-definite programming. Since semi-definite optimization problems play an important role in the sums-of-square approximation algorithms described above, it is important to be aware of the current complexity status of this problem. As noted above, while interior points algorithms for solving semi-definite programming problems are extremely efficient in practice, there is no definite result known placing the semi-definite programming problem in the class P. Khachiyan and Prokolab BIB001 proved that there exists a polynomial time algorithm for semi-definite programming in case the dimension is fixed. Using results proved by Ramana BIB002 on exact semi-definite duality theory, it can be deduced (see BIB004 ) that semi-definite feasibility cannot be NP-complete unless NP = co-NP (a hypothesis not believed to be true). In the Blum-Shub-Smale model of computation over real machines BIB003 , the semi-definite feasibility problem is clearly in the class NP R , and it is unknown if it is any easier than ordinary real polynomial feasibility problem in this model.