Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem C.15 — Characterisation of the CSinglAIP reduction

Open
AbelianPromises.Dichotomy.Supplement.csinglaip_characterisation

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

complexity-theoryminionsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1pcsp

Let (R,Q)(R,Q)(R,Q) and (S,T)(S,T)(S,T) be finite ternary promise templates: R→QR\to QR→Q and S→TS\to TS→T. Suppose that TTT contains no constant tuple. The specific constraint singleton AIP transformation of Definition C.13 is a polynomial-time reduction exactly when there exists an arity- and minor-preserving map

PCSP⁡(R,Q)≤CSinglAIPPCSP⁡(S,T)⟺ωCSinglAIP(Pol⁡(S,T))→Pol⁡(R,Q).\operatorname{PCSP}(R,Q)\le_{\mathrm{CSinglAIP}}\operatorname{PCSP}(S,T) \quad\Longleftrightarrow\quad \omega_{\mathrm{CSinglAIP}}(\operatorname{Pol}(S,T))\to\operatorname{Pol}(R,Q).PCSP(R,Q)≤CSinglAIP​PCSP(S,T)⟺ωCSinglAIP​(Pol(S,T))→Pol(R,Q).

The transformation first forms LC⁡(I)\operatorname{LC}(I)LC(I) using the source template's domains, prunes constraint tuples by singleton AIP to a fixed point, and applies the universal SSS-gadget to the residual Label Cover instance. Rejection outputs the single-variable instance with constraint (x,x,x)(x,x,x)(x,x,x). The left side requires both YES and NO preservation and a fixed finite program with polynomial step bounds for this construction. The right side is a family at every nonempty finite arity commuting with every minor map. The polymorphisms use the actual relation domains.

This companion theorem characterizes the entire reduction class and is not used in the proof of the mission's dichotomy goal. No symmetry, nonempty-relation, group, prime, rounding, or bounded-arity-cutoff assumption is added. Empty template domains and relations are included, with unsatisfiable intermediate data handled explicitly.

Differences from the source:

  • encoding: arbitrary nonempty finite coordinate and column sets → all nonempty finite subsets of Nat for coordinates and Fin(j+1) for arbitrary finite columns; reason: a size-unbounded finite-set skeleton; bijective reindexing preserves every instance and minor.
  • encoding: minor operations and the omega construction → the exact graph of each derived minor operation; reason: the graph records the same fibre-sum matrix and restricted minor without assuming derived closure facts.
  • encoding: pruning to a fixed point and restricting domains → simultaneous tuple deletion for N0+1 rounds followed by all incident positional compatibility tests; reason: finite monotone deletion gives the same greatest fixed point, and fixed-point pinned feasibility makes all incident supports agree; isolated domains are unchanged.
  • encoding: empty initial domains or relations interpreted as unsatisfiable → kappa returns rejection for any empty current domain or relation, including an initially empty isolated domain; reason: makes the nonempty-domain LC construction total on empty templates without removing any satisfiable source instance.
  • encoding: the specified transformation Phi_S on finite instances → a polynomial-time bit machine outputs an instance isomorphic to the concrete quotient gadget Phi_S; reason: finite instances in the source have no prescribed variable or constraint numbering; both bijections preserve all ordered scopes, so this only specifies their encoding.
Preamble
import Mathlib
import Definitions.Def_AbelianPromises_Dichotomy_Supplement_Reduction
import Definitions.Def_AbelianPromises_Dichotomy_Supplement_SkeletalOmega

set_option autoImplicit false
Formal statement
namespace AbelianPromises.Dichotomy.Supplement

/-- Theorem C.15: both directions, arbitrary finite ternary promise templates.
No symmetry, nonempty-relation, group, or rounding hypothesis is added. -/
theorem csinglaip_characterisation
    {A B C D : Type} [Fintype A] [Fintype B] [Fintype C] [Fintype D]
    (R : Relation A) (Q : Relation B) (S : Relation C) (T : Relation D)
    (hRQ : Hom R Q) (hST : Hom S T)
    (hT : ∀ a : D, (fun _ : Fin 3 => a) ∉ T.rel ()) :
    CSinglAIPReduction R Q S T ↔
      HasMinionHom (omega (polPresentation S T hST)) (polPresentation R Q hRQ) := by sorry

end AbelianPromises.Dichotomy.Supplement
Source
Tamio-Vesa Nakajima, Zephyr Verwimp, Stanislav Živný, STOC 2027 submission #967 (October 2026). Canonical submission artifact; no arXiv pin or acceptance claim. printed p. 21 (PDF p. 22), Theorem C.15.

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