  We show that unless P=NP, there cannot be a polynomial-time algorithm that
finds a point within Euclidean distance $c^n$ (for any constant $c \ge 0$) of a
local minimizer of an $n$-variate quadratic function over a polytope. This
result (even with $c=0$) answers a question of Pardalos and Vavasis that
appeared in 1992 on a list of seven open problems in complexity theory for
numerical optimization. Our proof technique also implies that the problem of
deciding whether a quadratic function has a local minimizer over an (unbounded)
polyhedron, and that of deciding if a quartic polynomial has a local minimizer
are NP-hard.
