# The Complexity of Computing KKT Solutions of Quadratic Programs

arXiv: https://arxiv.org/abs/2311.13738 · HTML: https://mlsanity.com/paper/2311.13738/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2023.

## Built on by (most cited first, 4 of 4)

- [The Complexity of Finding Local Optima in Contrastive Learning](https://mlsanity.com/paper/2509.16898/) (2025)
- [The Complexity of Min-Max Optimization for Quadratic Polynomials](https://mlsanity.com/paper/2606.17000/) (2026)
- [On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2409.10323/) (2024)
- [On Approximate Computation of Critical Points](https://mlsanity.com/paper/2601.21917/) (2026)

## Abstract (arXiv)

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 = PPADcapPLS.