Skip to content
DraconiticResearch
Search Sources API
186,123 studies31 sourcesUpdated 9 min ago
PreprintCC0arXiv

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

  • Argyrios Deligkas
  • Michail Fasoulakis
  • Stavros D. Ioannidis
Open at sourcePDFDOICite

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.

Related

  1. Treewidth and the complexity of box-constrained quadratic programs
    Alberto Del Pia, Aida Khajavirad
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. Polynomially Solvable Cases of the Quadratic Binary Optimization Problem with a Fixed Cardinality Constraint
    Thi Thanh Tu Le, Thorsten Koch
    arXivPreprintCC BY-NC-SA 4.0Full textOptimisation & controlarXiv
  3. Ergodic Linear-Quadratic Optimal Control with Stochastic Coefficients
    Xuyang Lin, Nizar Touzi
    arXivPreprintarXiv licenceFull textOptimisation & controlProbabilityarXiv
  4. Dynamical Systems and Nonconvex Quadratic Programs
    Nguyen Nang Thieu
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. A bounded degree SDSOS hierarchy for solving SPLD polynomial programs
    Chengmiao Yang, Liguo Jiao, Jae Hyoung Lee
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{deligkas2026complexity,
  title = {{The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients}},
  author = {Argyrios Deligkas and Michail Fasoulakis and Stavros D. Ioannidis},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.03945},
  eprint = {2611.03945},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03945},
  note = {CC0},
}
RIS
TY  - UNPB
TI  - The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients
AU  - Argyrios Deligkas
AU  - Michail Fasoulakis
AU  - Stavros D. Ioannidis
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2611.03945
UR  - https://arxiv.org/abs/2611.03945
AB  - 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.
ER  -