Theorem C.3 — Continuous-LocalOpt reduces to -Hölder-LocalOpt
ProvedNadlerCLS.theorem_C_3clscomplexity-theorycontinuous-local-searchfixed-pointsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1set-valued-contractions
For every fixed dimension and every fixed rational there is a polynomial-time many-one reduction
on . In the paper the target instance is .
Differences from the source:
- generalization: the problems printed on (Definitions 1, 2, 5) → every fixed dimension , the problems on ; reason: Appendix C proves the reductions on (p.34: "for generality"; p.37: "works for any polynomial dimension n"); is the printed case
- encoding: circuits with the ranges , (and , ) → raw circuit outputs clipped to these ranges with ; reason: Remark C.7's coordinate-wise clipping; it leaves every in-range instance unchanged
- encoding: answers are points of the cube, parameters rational in binary → answers are tagged rational points (
encNattag followed byencVectors); reductions are the publicCardinalMatching.SearchReduces(polynomial-time on Cook's Turing machines, every target answer decoded); reason: p.7's computational model: rational data in binary, polynomial-time many-one reductions with a decoder for every valid solution
Preamble
import Mathlib import Definitions.Def_NetworkEquilibriumCLS_LinearNash_Complexity import Definitions.Def_NadlerCLS_coSearch import Definitions.Def_NadlerCLS_holderSearch set_option autoImplicit false
Formal statement
namespace NadlerCLS
open NetworkEquilibriumCLS.LinearNash
/-- **Theorem C.3: Continuous-LocalOpt reduces to β-Hölder-LocalOpt** (Xiong–Vlatakis-Gkaragkounis, *On the Complexity of Finding Fixed Points for Set-Valued
Contractions*, arXiv:2609.14101, held version of 2026-11-03, sha256 1fcc5a02…6dc485,
Theorem C.3, p.36: "For every fixed rational β ∈ (0, 1], there is a polynomial-time
reduction from CONTINUOUS-LOCALOPT to β-HÖLDER-LOCALOPT"). For every `n ≥ 1` and rational
`β ∈ (0, 1]`, Continuous-LocalOpt on `[0, 1]ⁿ` reduces to β-Hölder-LocalOpt on `[0, 1]ⁿ` by a
polynomial-time search reduction.
**Formalization Note** Printed for Definitions 2 and 5, proved on `[0, 1]ⁿ` (p.37). -/
theorem theorem_C_3 (n : ℕ) (hn : 1 ≤ n) (β : ℚ) (hβ0 : 0 < β) (hβ1 : β ≤ 1) :
SearchReduces (coSearch n) (holderSearch n β) := by sorry
end NadlerCLS
Source
Xiong–Vlatakis-Gkaragkounis, On the Complexity of Finding Fixed Points for Set-Valued Contractions, arXiv:2609.14101 (held version of 2026-11-03, sha256 1fcc5a027ffe65205e4ef9a9ef7730f6f07fe3f7006447cac39a7562e36dc485), Theorem C.3, p.36
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.