Could exact SDP be a computationally hard problem?
S.Tarasov (speaker) and M.Vyalyi
We conjecture that the Exact Semidefinite Programming Problem (ESDP):
to check whether some affine subspace of square matrices with rational
entries intersects the cone of positive semidefinite matrices, could be intrinsically
difficult contrary to the intuiton that the problem is convex and some of its approximate
versions are effectively solvable.
Specifically we show how to reduce to ESDP the well-known problem of
comparing numbers represented by arithmetic circuits.
The last problem is considered to be difficult and from algorithmic
viewpoint is equivalent according to Allender E. et al (2005) to the
generic task of numerical computation. Thus the comparison problem lowerbounds ESDP.
The result essentially uses the exact duality theory for SDP obtained
earlier by Ramana M. (1997). We plan to discuss related matters and, in particular, whether it is
possible to use some different mathematical programming problems in order to simulate the comparison problem.