**Monday, 14:15 - 14:40 h, Room: H 2038**

**Peter Dickinson**

Considering the complexity of complete positivity using the Ellipsoid method

**Coauthors: Kurt M. Anstreicher, Samuel Burer, Luuk Gijben**

**Abstract:**

Copositive programming has become a useful tool in dealing with all sorts of optimisation problems. It has however been shown by Murty and 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 dual cone to the copositive cone is called the completely positive cone, and, because of this result on the copositive cone, it has widely been assumed that the strong membership problem for this cone would be an NP-complete problem. The proof to this has however been lacking. In order to show that this is indeed true we would need to show that the problem is both an NP-hard problem and a problem in NP. In this talk we use the Ellipsoid Method to show that this is indeed an NP-hard problem and that the weak membership problem for the completely positive cone is in NP (where we use a natural extension of the definition of NP for weak membership problems). It is left as an open question as to whether the strong membership problem itself is in NP.

Talk 3 of the invited session Mon.2.H 2038

**"Nonlinear semidefinite programs and copositive programs"** [...]

Cluster 4

**"Conic programming"** [...]