Project 2: Is Semi-Definite Programming (SDP) Polynomial-Time Solvable?

Semi-Definite Programming (SDP) is an extension of Linear Programming (LP), with vector variables replaced by matrix variables and nonnegativity elementwise replaced by positive semidefiniteness.

It is known that LP is solvable in polynomial time. SDP shares some good properties of LP, yet it has more challenging difficulties.

In 2014, the well-known TCS blog Gödel’s Lost Letter and P=NP posted one article about this topic: Could We Have Felt Evidence For SDP ≠ P?

In this project, we would like to collect theoretical obstacles that prevent us to get a truly polynomial-time algorithm for SDP in several aspects and discuss how to make any new progress.

(1) The Complexity of Square-Root Sum 

In 1976, Ron Graham, Michael Garey, and David Johnson could not show some geometric optimization problems such as Euclidean Traveling Salesman Problem is NP-complete or not (they can only show the problem is NP-hard), the reason is that they could not show whether the square-root-sum problem is polynomial-time solvable or not. link

In 1998, Michel X. Goemans gave an ICM talk, in which, he addressed this issue: “Semidefinite programs can be solved(or more precisely, approximated) in polynomial-time within any specific accuracy either by the ellipsoid algorithm or more efficiently through interior-point algorithms…The above algorithms produce a strictly feasible solution(or slightly infeasible for some versions of the ellipsoid algorithm) and, in fact, the problem of deciding whether a semidefinite program is feasible(exactly) is still open. A special case of semidefinite programming feasibility is the square-root-sum problem. The complexity of this problem is still open.” link 

The most remarkable progress towards this problem is by Eric Allender and his co-authors, in 2003, they showed this problem lies in the 4th level of the Counting Hierarchy. link

In CCC 2019 workshop open problem session, I presented the square-root sum problem, Eric Allender was also in the audience, he commented “we still embarrassingly have little understanding of it. ”

I also asked Mihalis Yannakakis about the connection of square-root sum and PosSLP in Papafest, he kindly explained more details: 

“PosSLP is a problem, not a class, which encapsulates the essential power of the unit-cost arithmetic RAM model. Basically, the corresponding class is the class of decision problems solvable in polynomial time in the Blum-Shub-Smale model with rational constants.  The paper by Allender et al is the best reference for PosSLP. That paper introduced and studied thoroughly the problem. There is no further progress with respect to its relation to the classical complexity classes, like NP, Polynomial hierarchy, etc, as far as I know.

The square-root sum problem is reducible to PosSLP, but it is not known to be equivalent.
That is if someone proves that the square-root sum problem is in P or NP
(in the standard Turing model of complexity), it will not follow from this that PosSLP is also in P or NP, from what we know today.

There are some problems that are equivalent to PosSLP (i.e. reductions going both ways),
for example, one is in my paper with Etessami on Recursive Markov chains in JACM 2009, another in the paper with Etessami and Stewart in our paper on Branching processes in SIAM J. Computing 2017.”

More links: 

complexity of square-root sum

TOPP Problem 33

The Curse of Euclidean Metric: Square Roots

(2) Logic and P 

In his Ph.D. thesis, Ronald Fagin created the area of Finite Model Theory and stated that the set of all properties expressible in existential second-order logic is precisely the complexity class NP (It is known as Fagin’s Theorem). Link

It is a long open problem in descriptive complexity that what logic structure can capture P?  The logic FPC (Fixed-Point Logic with Counting) is a powerful and natural fragment of P, but it is not all of P.  Jin-Yi Cai, Martin Fürer and Neil Immerman found one counterexample link . It is also known that FPC could not express the solvability of systems of linear equations over a finite field. However, Martin Grohe showed that for every surface, a property of graphs embeddable in that surface is decidable in polynomial time if and only if it is definable in FPC link .

Matthew Anderson, Anuj Dawar and  Bjarki Holm showed that the optimization of linear programs is expressible in FPC link. Then, how about SDP?  Anuj Dawar and Pengming Wang showed the FPC implementation of the ellipsoid method extends to semidefinite programs (subject to some technical conditions) link.

How does that new progress help us to understand the complexity of SDP?

(3) Semialgebraic Proof System 

In the recent paper Semialgebraic Proofs and Efficient Algorithm Design published on Foundations and Trends in Theoretical Computer Science, Noah Fleming, Pravesh Kothari and Toniann Pitassi bridge Semialgebraic Proofs and Efficient Algorithm Design. It is amazing that some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself! That paper mainly discusses two semialgebraic proof systems– Sherali-Adams and Sum-of-Squares, and shows up to an additive small error, SDP can be solvable in polynomial time (Corollary 3.12).

What proof system is strong enough to capture the nature of SPD? Is there any hope we can get a truly polynomial-time algorithm to solve SDP with it? Paul Beame discussed the limit of proof in the open lecture of the Simons Institute: The Limits of Proof.

(4) Tropical Geometry and Algebraic Geometry

In recent years, there has been some surprising new progress towards some fundamental open problems in linear programming with the help of tropical and algebraic geometry.  For example, Michael Joswig disproved the continuous analogue of Hirsch conjecture and showed primal-dual log-barrier interior point methods are not strongly polynomial together with other coauthors using an amazing new technique–Tropical Geometry link.  Jesús A. De Loera gave a talk of their new contributions of simplicial polytopes and central path curvature with tropical and algebraic geometry tools in JMM 2019 link.

Pablo A. Parrilo also showed the connection of SDP and convex algebraic geometry link.

Can those tools help to get a truly polynomial-time algorithm of SDP?

(5) Exact Computation and Number Theory

Yuan Zhou (University of Kentucky) suggested the interval approximate method from the exact computation area to handle the square-root sum problem.  Yuan Zhou has a series of excellent papers about function generating together with her Ph.D. advisor. It is interesting to ask if one can generate a function related to square-root sum efficiently, is that helpful to say something about its complexity? (In P or in NP? )

Qi Cheng (University of Oklahoma) suggested applying diophantine approximation from number theory to improve the square-root sum problem.  What is the minimum nonzero difference between two sums of square roots of integers? Qi Cheng, Xianmeng Meng, Celi Sun, and Jiazhe Chen gave a tighter upper bound link.

(6) Circuit Lower Bound and Other Consequences of SDP=P

Noah Fleming proposed one interesting research direction: instead of trying to put SDP into P, it might also be interesting to prove that putting SDP in P is hard! So like show that if SDP=P, then we get circuit lower bounds or derandomization or something.

Noah Fleming recommended the paper showing that complexity class separations imply circuit lower bounds by Nissan-Wigderson Generator Link and the Kabanets-Impagliazzo paper Link. Noah also attempted to connect this problem to degree 2 polynomial and SETH.

Thanks to the brilliant idea by Noah Fleming, this problem would connect to the hardcore areas of TCS–Circuit Lower Bound and Pseudorandoness!