Copositive programming has become a useful tool in dealing with all sorts of optimisation problems. It has however been shown by Murty and Kabadi [K.G. Murty and S.N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39, no.2:117–129, 1987] that the strong membership problem for the copositive cone, that is deciding whether or not a given matrix is in the copositive cone, is a co-NP-complete problem. The question of whether or not the strong membership problem for the dual of the copositive cone, the completely positive cone, is also an NP-hard problem has so far been left open. In this paper it is proven that the strong membership problem for the completely positive cone is in fact NP-hard. Furthermore, it is shown that even the weak membership problems for both of these cones are NP-hard. We also present an alternative proof of the NP-hardness of the strong membership problem for the copositive cone.
Citation
Johann Bernoulli Institute for Mathematics and Computer Science, University of Groningen, The Netherlands, April 2011