Paperlane

no. 8 · Wednesday 4 November 2026

The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients

Argyrios Deligkas, Michail Fasoulakis and Stavros D. Ioannidis

math.OC · via cs.CC

Abstract

Computing a Karush-Kuhn-Tucker (KKT) point of a quadratic polynomial over the unit hypercube is known to be $CLS$-complete, when the coefficients of the polynomial are encoded in binary. We prove that the problem remains $CLS$-complete even when the coefficients are encoded in unary. This is the first problem proven to remain $CLS$-hard when the input is given in unary.

fields
Optimization and Control
pdf ↗ page arXiv:2611.03945 ↗