All kinds of combinatorial optimization problems can be formulated in terms of matrices with nonnegative entries, and can therefore be tackled using copositive programming. A matrix is copositive when it remains nonnegative under conjugation with nonnegative vectors. For example, any quadratic program with both binary and linear constraints can be rewritten as a copositive program. Deciding whether a matrix is copositive is co-NP-complete.

The dual notion of a copositive matrix is a completely positive matrix (that is, a matrix that has a square root with nonnegative entries). It is widely believed that deciding whether a matrix is completely positive is NP-hard, but this was never proven. This paper establishes that folk theorem in several variations: given a matrix, is it exactly/approximately copositive/completely positive? In all four cases, the problem is shown to be NP-hard by finding reductions from the independent set problem for graphs, which is known to be NP-hard.

This paper fills a gap in the literature satisfactorily. It is left open if deciding whether a matrix is completely positive is NP-complete.