# On the complexity of finding a local minimizer of a quadratic function over a polytope

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Aug 2020.

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

- [SoS1: O1 and R1-Like Reasoning LLMs are Sum-of-Square Solvers](https://mlsanity.com/paper/2502.20545/) (2025)
- [Higher-Order Newton Methods with Polynomial Work per Iteration](https://mlsanity.com/paper/2311.06374/) (2023)
- [Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms](https://mlsanity.com/paper/2302.12261/) (2023)
- [Adaptive Conditional Gradient Descent](https://mlsanity.com/paper/2510.11440/) (2025)
- [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)
- [Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses](https://mlsanity.com/paper/2605.10219/) (2026)

## Abstract (arXiv)

We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance cn (for any constant c ≥ 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.