Paperlane

no. 9 · Thursday 5 November 2026

On the Complexity of Finding Fixed Points for Set-Valued Contractions

Emmanouil-Vasileios Vlatakis-Gkaragkounis and Pucheng Xiong

math.GN · v4 · 58 pp

Abstract

We study the computational complexity of finding fixed points of set-valued contractions. We first formulate a computational problem for Nadler's fixed-point theorem, PROJECTED-NADLER, and prove that it is CLS-complete by showing its equivalence to CONTINUOUS-LOCALOPT. We then establish a stronger converse to Nadler's theorem, which can be applied as a tool to analyze the convergence rate of the set-valued basic iteration procedure. Finally, we reduce the large-margin triplet stationarity problem to PROJECTED-NADLER. Combining the argument for CLS-hardness of exact triplet stationarity problem [Yan et al. 2025] with the CLS-hardness of approximate KKT points of quadratic programs [Fearnley et al. 2025], we obtain CLS-completeness of large-margin triplet stationarity at any prescribed accuracy.

comments
58 pages, 4 figures
fields
General Topology
pdf ↗ page arXiv:2609.14101 ↗