A note on the computation of the CP-rank

The purpose of this note is to address the computational question of determining whether or not a square nonnegative matrix (over the reals) is completely positive and finding its CP-rank when it is. We show that these questions can be resolved by finite algorithms and we provide (non-polynomial) complexity bounds on the number of arithmetic/Boolean operations that these algorithms require. We state several open questions including the existence of polynomial algorithms to resolve the above problems and availability of algorithms for addressing complete positivity over the rationals and over (0, 1) matrices. (c) 2006 Elsevier Inc. All rights reserved.