Abstract
It is well known that solving a (non-convex) quadratic program is NP -hard. We show that the problem remains hard even if we are only looking for a Karush–Kuhn–Tucker (KKT) point, instead of a global optimum. Namely, we prove that computing a KKT point of a quadratic polynomial over the domain [0,1] n is complete for the class CLS = PPAD ∩ PLS .
Funding Information
  • EPSRC (EP/W014750/1, EP/X040461/1)
  • Swiss State Secretariat for Education, Research and Innovation (MB22.00026)

This publication has 37 references indexed in Scilit: