Semidefinite programming and arithmetic circuit evaluation. (English) Zbl 1163.90694
Summary: We address the exact semidefinite programming feasibility problem (SDFP) consisting in checking that intersection of the cone of positive semidefinite matrices and some affine subspace of matrices with rational entries is not empty. SDFP is a convex programming problem and is often considered as tractable since some of its approximate versions can be efficiently solved, e.g. by the ellipsoid algorithm.
We prove that SDFP can decide comparison of numbers represented by the arithmetic circuits, i.e. circuits that use standard arithmetical operations as gates. Our reduction may give evidence to the intrinsic difficulty of SDFP (contrary to the common expectations) and clarify the complexity status of the exact SDP-an old open problem in the field of mathematical programming.
We prove that SDFP can decide comparison of numbers represented by the arithmetic circuits, i.e. circuits that use standard arithmetical operations as gates. Our reduction may give evidence to the intrinsic difficulty of SDFP (contrary to the common expectations) and clarify the complexity status of the exact SDP-an old open problem in the field of mathematical programming.
MSC:
| 90C22 | Semidefinite programming |
References:
| [1] | E. Allender, P. Brügiser, J. Kjeldgaard-Petersen, P. Mitersen, On the complexity of numerical analysis, ECCC, TR-37, 2005.; E. Allender, P. Brügiser, J. Kjeldgaard-Petersen, P. Mitersen, On the complexity of numerical analysis, ECCC, TR-37, 2005. |
| [2] | Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1998), Springer: Springer New York |
| [3] | Cucker, F.; Grigoriev, D., On the power of real Turing machines over binary inputs, SIAM J. Comput., 26, 243-254 (1997) · Zbl 0874.68110 |
| [4] | Grötshel, M.; Lovaśz, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1988), Springer: Springer New York · Zbl 0634.05001 |
| [5] | Karmarkar, N., A new polynomial algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065 |
| [6] | Khachiyan, L., A polynomial algorithm in linear programming, Soviet Math. Dokl., 20, 191-194 (1979) · Zbl 0409.90079 |
| [7] | P. Koiran, Valiant’s model and the cost of computing integers, ECCC, TR-03, 2004.; P. Koiran, Valiant’s model and the cost of computing integers, ECCC, TR-03, 2004. · Zbl 1061.68062 |
| [8] | Nesterov, Yu. E.; Nemirovskii, A. S., Interior Point Methods in Convex Optimization: Theory and Applications (1994), SIAM Publications: SIAM Publications Philadelphia |
| [9] | Porkolab, L.; Khachiyan, L., On the complexity of semidefinite programs, J. Global Optim., 10, 351-365 (1997) · Zbl 0881.90127 |
| [10] | Ramana, M. V., An exact duality theory for semidefinite programming and its complexity implications, Math. Program., 77, 129-162 (1997) · Zbl 0890.90144 |
| [11] | Renegar, J., A polynomial-time algorithm based on Newton’s method for linear programming, Math. Program., 40, 59-94 (1988) · Zbl 0654.90050 |
| [12] | Renegar, J., A Mathematical View of Interior-point Methods in Convex Optimization (2001), SIAM Publications: SIAM Publications Philadelphia · Zbl 0986.90075 |
| [13] | A. Schönhage, On the power of random access machines, in: H. Maurer (Ed.), Automata, Languages and Programming ICALP 79, Lecture Notes in Computer Science, vol. 71, Springer, New York, 1979, pp. 520-529.; A. Schönhage, On the power of random access machines, in: H. Maurer (Ed.), Automata, Languages and Programming ICALP 79, Lecture Notes in Computer Science, vol. 71, Springer, New York, 1979, pp. 520-529. · Zbl 0409.68030 |
| [14] | Shub, M.; Smale, S., On the intractability of Hilbert’s Nullstellensatz and an algebraic version of “\( \text{NP} \neq \text{P} \)”, Duke Math. J., 81, 47-54 (1996) · Zbl 0882.03040 |
| [15] | Sipser, M., Introduction to the Theory of Computation (2005), Thomson Course Technology: Thomson Course Technology Boston |
| [16] | Valiant, L. G., Completeness classes in algebra, (Proceedings of the11th ACM Symposium on Theory of Computing (1979), ACM Press: ACM Press New York), 249-261 |
| [17] | Wagner, K., The complexity of combinatorial problems with succinct input representation, Acta Inform., 23, 325-356 (1986) · Zbl 0621.68032 |
| [18] | H. Wolkowicz, R. Saigal, L. Vandenberghe (Eds.), Handbook of Semidefinite Programming, Kluwer Academic Publishers, Dordrecht, 2000.; H. Wolkowicz, R. Saigal, L. Vandenberghe (Eds.), Handbook of Semidefinite Programming, Kluwer Academic Publishers, Dordrecht, 2000. · Zbl 0951.90001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
