Several NP-complete problems can be turned into convex problems by formulating them as optimization problems over the copositive cone. Unfortunately checking membership in the copositive cone is a co-NP-complete problem in itself. To deal with this problem, several approximation schemes have been developed. One of them is a hierarchy of cones introduced by P. Parrilo. Membership of these cones can be checked by deciding whether a certain polynomial can be written as a sum of squares, which can be done via semidefinite programming. It is known that for matrices of order n < 5 the zero order Parrilo cone is equal to the copositive cone. In this talk we will investigate the relation between the hierarchy and the copositive cone for order n > 4. In particular a surprising result is found for the case n = 5, establishing a direct link between the copositive cone and the semidefinite cone of that order. |