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. I know that in general I cannot claim that I have a polynomial time algorithm for my decision problem. But if I know that the feasible space of my SDP lies in the convex hull of a finite set of rank-$1$ matrices (having only rational entries), then does the situation improve in my favor or is it still as bad as the general case? Is it wishful thinking that the SDP in this case can be solved exactly?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top