I've been trying to attack the problem posted here, about quickly checking if a matrix has any positive semidefinite completions. I suspect that the answer to the question is "no", because known methods for checking positive semidefinite program feasibility work slower than required or only on certain kinds of matrices, and moreover we're asked to check for existence of completions faster than we could check any candidate matrix for being positive semidefinite. So I wonder if there are any known lower complexity bounds on solving positive semidefinite programs. I couldn't find anything on Google Scholar.
