I have a decision problem that I have formulated as a feasibility SDP. The answer to the decision problem depends on whether the SDP is feasible or not. It is known that a SDP can be solved to arbitrary precision in time that is polynomial in the input size as well as the precision value. Now can I claim that I have a polynomial time algorithm for my decision problem?



SDP Feasibility
No, you can't. If you could, then you would, among other things, have a solution to what is known as the [square root problem](http://garden.irmacs.sfu.ca/?q=op/complexity_of_square_root_sum): given $a\_1, \ldots, a\_n,k$ determine whether $ \sum\_{i=1}^n \sqrt{a\_i} \leq k.$ This looks like a solvable problem - just compute the square roots- but is actually difficult, because its unclear to what precision the square roots need to be computed. Now observe that this is equivalent to asking whether there is a point $(z\_1, \ldots, z\_n)$ that makes the following SDP feasible: 


$$ \sum\_{i=1}^n z\_i \leq k, ~~~z\_i \geq 0, ~~~~\left( \matrix{ 1 & z\_i \cr z\_i & a\_i} \right) \preceq 0$$


Finally, I suspect you would get better answers if you ask on [cstheory.stackexchange.com](https://cstheory.stackexchange.com/), which is visited by many of the experts on these sorts of questions. 


