  A polynomial optimization problem (POP) asks for minimizing a polynomial
function given a finite set of polynomial constraints (equations and
inequalities). This problem is well-known to be hard in general, as it encodes
many hard combinatorial problems. The Lasserre hierarchy is a sequence of
semidefinite relaxations for solving (POP). Under the standard archimedean
condition, this hierarchy is guaranteed to converge asymptotically to the
optimal value of (POP) (Lasserre, 2001) and, moreover, finite convergence holds
generically (Nie, 2012). In this paper, we aim to investigate whether there is
an efficient algorithmic procedure to decide whether the Lasserre hierarchy of
(POP) has finite convergence. We show that unless P=NP there cannot exist such
an algorithmic procedure that runs in polynomial time. We show this already for
the standard quadratic programs. Our approach relies on characterizing when
finite convergence holds for the so-called Motzkin-Straus formulation (and some
variations of it) for the stability number of a graph.
