Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The instance map (f,p,δ,λ)↦(f,p,δ,λ′)(f,p,\delta,\lambda)\mapsto(f,p,\delta,\lambda')(f,p,δ,λ)↦(f,p,δ,λ′) with λ′≥nλ\lambda'\ge n\lambdaλ′≥nλ of Theorem C.3 is polynomial-time

Proved
NadlerCLS.scaleLam_polyTime

by utkuokur · Nov 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

clscomplexity-theorycontinuous-local-searchfixed-pointsset-valued-contractions

Fix a dimension nnn. An instance of Continuous-LocalOpt, or of β\betaβ-Hölder-LocalOpt, on [0,1]n[0,1]^n[0,1]n is a tuple I=(f,p,δ,λ)I=(f,p,\delta,\lambda)I=(f,p,δ,λ) of two arithmetic circuits and two positive rational parameters, given by its binary code enc⁡(I)\operatorname{enc}(I)enc(I).

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 FFF on binary strings, computable in polynomial time by a deterministic one-tape Turing machine, such that for every valid instance (f,p,δ,λ)(f,p,\delta,\lambda)(f,p,δ,λ) there is a rational number λ′\lambda'λ′ with

λ′  ≥  nλandF(enc⁡(f,p,δ,λ))  =  enc⁡(f,p,δ,λ′).\lambda'\;\ge\; n\lambda \qquad\text{and}\qquad F\bigl(\operatorname{enc}(f,p,\delta,\lambda)\bigr)\;=\;\operatorname{enc}(f,p,\delta,\lambda').λ′≥nλandF(enc(f,p,δ,λ))=enc(f,p,δ,λ′).

The circuits fff and ppp and the parameter δ\deltaδ are left unchanged; only the last parameter is enlarged.

This is the instance-map half of the reduction from Continuous-LocalOpt to β\betaβ-Hölder-LocalOpt. With t=∥x−y∥1≤nt=\lVert x-y\rVert_1\le nt=∥x−y∥1​≤n, a violation ∥f(x)−f(y)∥1>λ′tβ\lVert f(x)-f(y)\rVert_1>\lambda' t^{\beta}∥f(x)−f(y)∥1​>λ′tβ of the Hölder bound of the constructed instance is a violation ∥f(x)−f(y)∥1>λt\lVert f(x)-f(y)\rVert_1>\lambda t∥f(x)−f(y)∥1​>λt of the Lipschitz bound of the original instance.

Differences from the source:

  • weakening: the paper's target instance is (f,p,δ,nλ)(f,p,\delta,n\lambda)(f,p,δ,nλ) (p.37) → any λ′≥nλ\lambda'\ge n\lambdaλ′≥nλ is allowed, and λ′\lambda'λ′ may depend on the instance; reason: the proof of Theorem C.3 only uses λ′≥nλ\lambda'\ge n\lambdaλ′≥nλ, and the paper's choice λ′=nλ\lambda'=n\lambdaλ′=nλ satisfies the statement
  • generalization: the statement is made for every n≥0n\ge 0n≥0; for n≤1n\le 1n≤1 the identity map already satisfies it
  • encoding: FFF 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 δ>0\delta>0δ>0, λ>0\lambda>0λ>0. The code is encCO.

Preamble
import Mathlib
import Definitions.Def_NetworkEquilibriumCLS_LinearNash_Complexity
import Definitions.Def_NadlerCLS_COInstance

set_option autoImplicit false
Formal statement
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
Source
Xiong–Vlatakis-Gkaragkounis, On the Complexity of Finding Fixed Points for Set-Valued Contractions, arXiv:2609.14101v4 (3 Nov 2026), https://arxiv.org/abs/2609.14101, 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"); Section 2, p.7 (polynomial-time many-one reductions).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me