Theorem 1.11 — Both natural Avoid-family consequences for graphs and lattices
OpenAMRangeAvoid.Characterization.Supplement.theorem_1_11complexity-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 for the published verifier. Their literal compositions define the two expanding-circuit families and . With the same factor for and , their independent consequences are
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