**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.