As mentioned by Robert Bryant, in the $n = 3$ case, checking that the matrix is positive semidefinite and has all entries $\geq 0$ is both necessary and sufficient. In fact, the same is true when $n = 4$, but this is only a necessary (not sufficient) test for complete positivity when $n \geq 5$ (see "L. J. Gray and D. G. Wilson. Nonnegative Factorization of Positive Semidefinite Nonnegative Matrices. *Linear Algebra Appl.*, 31:119-127, 1980", for example).

When $n \geq 5$, things get harder (NP-hard), but there are still *some* things that you can do, at least for small $n$. The usual approach is to approximate the set of completely positive matrices from the outside by other convex cones of matrices:

$\mathcal{K}_0 \supset \mathcal{K}_1 \supset \mathcal{K}_2 \supset\cdots \supset \mathcal{C},$

where $\mathcal{C}$ is the set of completely positive matrices, $\mathcal{K}_0$ is the set of "doubly-nonnegative matrices" (i.e., positive semidefinite matrices that also have all entries $\geq 0$, which were mentioned earlier), and $\mathcal{K}_i$ for $i \geq 1$ are better and better approximations of $\mathcal{C}$ (and in particular, $\lim_{i \rightarrow \infty} \mathcal{K}_i = \mathcal{C}$). Furthermore, the $\mathcal{K}_i$'s are defined in such a way that determining whether or not a matrix is a member of $\mathcal{K}_i$ can be phrased as a semidefinite program, and is thus computationally tractable for small $n$ and small $i$ (the semidefinite program takes more and more effort to solve as $i$ increases). I'm having trouble tracking down the original paper that discusses how the $\mathcal{K}_i$'s are defined, but "J. Povh and F. Rendl. Copositive and semidefinite relaxations of the quadratic assignment problem. *Discrete Optimization*, 9:231-241, 2009" goes over these things in Section 3.

The upshot of this is that, in practice, we can determine when a matrix is *not* completely positive, by showing that is it not a member of $\mathcal{K}_i$ for some $i$. However, I am not aware of any methods for proving that a matrix *is* completely positive that work very well in practice.

2more comments