Let $E$ be a subset of entries of a real symmetric $n \times n$ matrix. We want to find a positive-definite matrix $X$ such that $X_{i,j}=M_{i,j}$ for all $(i,j) \in E$ for a fixed positive semidefinite matrix $M$. Assume we know that such $X$ exists for the given $E$ and $M$.
What (and how much) is numerically harder: to compute $X$ or to check, whether a given completion is positive definite?
Intuitively, it seems that checking should be easier than completing. However, as far as I understood, checking whether matrix is PD numerically boils down to computing its Cholesky decomposition (complexity $\mathcal{O}(n^3)$). On the other hand, completion of $X$ is an example of a semidefinite optimization problem which can be solved in polynomial time up to desired accuracy, but a priori, this does not mean that it is more complex than $\mathcal{O}(n^3)$.