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.