The instance map with of Theorem C.3 is polynomial-time
ProvedNadlerCLS.scaleLam_polyTimeFix a dimension . An instance of Continuous-LocalOpt, or of -Hölder-LocalOpt, on is a tuple of two arithmetic circuits and two positive rational parameters, given by its binary code .
The lemma states that the instance construction in the proof of Theorem C.3 can be carried out in polynomial time on codes: there is a map on binary strings, computable in polynomial time by a deterministic one-tape Turing machine, such that for every valid instance there is a rational number with
The circuits and and the parameter are left unchanged; only the last parameter is enlarged.
This is the instance-map half of the reduction from Continuous-LocalOpt to -Hölder-LocalOpt. With , a violation of the Hölder bound of the constructed instance is a violation of the Lipschitz bound of the original instance.
Differences from the source:
- weakening: the paper's target instance is (p.37) → any is allowed, and may depend on the instance; reason: the proof of Theorem C.3 only uses , and the paper's choice satisfies the statement
- generalization: the statement is made for every ; for the identity map already satisfies it
- encoding: is a function on all binary strings and is constrained only on codes of valid instances
Formalization Note PolyTime is the public alias of CookPvsNP.PolyTimeComputable. An instance is valid (COInstance.Valid) if both circuits are well-behaved with the right numbers of inputs and outputs and , . The code is encCO.
import Mathlib import Definitions.Def_NetworkEquilibriumCLS_LinearNash_Complexity import Definitions.Def_NadlerCLS_COInstance set_option autoImplicit false
namespace NadlerCLS
open NetworkEquilibriumCLS.LinearNash
/-- **The instance map of Theorem C.3 is polynomial-time** (Xiong–Vlatakis-Gkaragkounis, *On the
Complexity of Finding Fixed Points for Set-Valued Contractions*, arXiv:2609.14101v4, proof of
Theorem C.3, p.37: "We construct the β-HÖLDER-LOCALOPT instance I_HO := (f, p, δ, nλ). This
construction clearly has polynomial size"). Some polynomial-time computable map on binary strings
sends the code of every valid instance `(f, p, δ, λ)` on `[0, 1]ⁿ` to the code of an instance
`(f, p, δ, λ')` with the same circuits, the same `δ`, and `λ' ≥ n λ`.
**Formalization Note** The paper takes `λ' = n λ`; the proof of Theorem C.3 only uses
`λ' ≥ n λ`, so any such `λ'` (which may depend on the instance) is allowed. The map is constrained
only on codes of valid instances. -/
theorem scaleLam_polyTime (n : ℕ) :
∃ F : List Bool → List Bool, PolyTime F ∧
∀ I : COInstance n, I.Valid →
∃ lam' : ℚ, (n : ℚ) * I.lam ≤ lam' ∧
F (encCO I) =
encCO ({ f := I.f, p := I.p, δ := I.δ, lam := lam' } : COInstance n) := by sorry
end NadlerCLS