Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.11 — Both natural Avoid-family consequences for graphs and lattices

Open
AMRangeAvoid.Characterization.Supplement.theorem_1_11

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidance

There exist deterministic polynomial-time graph- and lattice-to-SSLB reduction programs and an SSLB targeted-hitting reduction (f,g)(f,g)(f,g) for the published verifier. Their literal compositions define the two expanding-circuit families fGNIf_{\mathrm{GNI}}fGNI​ and fSVPf_{\mathrm{SVP}}fSVP​. With the same factor γ(n)=400⌈n/log⁡2n⌉\gamma(n)=400\lceil\sqrt{n/\log_2 n}\rceilγ(n)=400⌈n/log2​n​⌉ for n≥2n\ge2n≥2 and γ(1)=400\gamma(1)=400γ(1)=400, their independent consequences are

AvoidfGNI∈SearchNP ⟹ GNI,GI∈NP∩coNP,\mathrm{Avoid}_{f_{\mathrm{GNI}}}\in\mathrm{SearchNP}\ \Longrightarrow\ \mathrm{GNI},\mathrm{GI}\in\mathrm{NP}\cap\mathrm{coNP},AvoidfGNI​​∈SearchNP ⟹ GNI,GI∈NP∩coNP, AvoidfSVP∈SearchNP ⟹ GapSVP‾γ∈prNP ∧ GapSVPγ∈prNP∩prcoNP.\mathrm{Avoid}_{f_{\mathrm{SVP}}}\in\mathrm{SearchNP}\ \Longrightarrow\ \overline{\mathrm{GapSVP}}_\gamma\in\mathrm{prNP}\ \land\ \mathrm{GapSVP}_\gamma\in\mathrm{prNP}\cap\mathrm{prcoNP}.AvoidfSVP​​∈SearchNP ⟹ GapSVP​γ​∈prNP ∧ GapSVPγ​∈prNP∩prcoNP.

This one item states the joint formal content of Corollaries 5.2 and 5.3, as referenced by introductory Theorem 1.11. Each implication requires only its own family-specific algorithm. The graph conclusions concern complementary total languages; the lattice conclusions concern promise classes.

Differences from the source:

  • encoding: the two composed families named in Corollaries 5.2 and 5.3 → existentially produced operational reduction maps and their literal compositions with a single SSLB Avoid producer; reason: existence and correctness of the programs are conclusions, and both family-specific implications are retained independently
  • encoding: graph inputs and the factor formula with log₂ n → the same decidable total graph-code extension and gamma(1)=400 used in Theorems 4.4 and 4.6; reason: the complementary graph languages agree on every graph pair, and exact dimension-one lattice inputs are retained
Preamble
import Definitions.Def_AMRangeAvoid_Characterization_Supplement_Families
import Definitions.Def_AMRangeAvoid_Characterization_SSLB
Formal statement
namespace AMRangeAvoid.Characterization.Supplement

theorem theorem_1_11 :
    ∃ graphMap latticeMap : Bits → Bits,
      DecisionMap GNI SSLB graphMap ∧
      DecisionMap (CoGapSVP gamma) SSLB latticeMap ∧
      ∃ f : Bits → Bits, ∃ g : Bits → Bits → Bits,
        IsAvoidReduction (TargetedHitting SSLB sslbVerifier) f g ∧
        (InSearchNP (AvoidFamily (composedFamily graphMap f)) →
          InPrNPCoNP GNI ∧ InPrNPCoNP GI) ∧
        (InSearchNP (AvoidFamily (composedFamily latticeMap f)) →
          InPrNP (CoGapSVP gamma) ∧ InPrNPCoNP (GapSVP gamma)) := by sorry

end AMRangeAvoid.Characterization.Supplement
Source
Zeyong Li, STOC 2027 submission #502 (October 2026), Theorem 1.11, printed p.5 (PDF p.7); formal content Corollaries 5.2–5.3, printed p.25 (PDF p.27); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/502.pdf

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