Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The specified CSinglAIP reduction with machine semantics

Definition
AbelianPromises_Dichotomy_Supplement_Reduction

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

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

The relation PCSP⁡(R,Q)≤CSinglAIPPCSP⁡(S,T)\operatorname{PCSP}(R,Q)\le_{\mathrm{CSinglAIP}}\operatorname{PCSP}(S,T)PCSP(R,Q)≤CSinglAIP​PCSP(S,T) means that the specific transformation ΦS\Phi_SΦS​ is a polynomial-time promise reduction. Its machine must output a representation of the concrete ΦS(I)\Phi_S(I)ΦS​(I) for every encoded input instance, send every RRR-satisfiable instance to an SSS-satisfiable one, and send every instance without a QQQ-solution to one without a TTT-solution:

I→R⟹ΦS(I)→S,I↛Q⟹ΦS(I)↛T.I\to R\Longrightarrow\Phi_S(I)\to S,\qquad I\not\to Q\Longrightarrow\Phi_S(I)\not\to T.I→R⟹ΦS​(I)→S,I→Q⟹ΦS​(I)→T.

Polynomial time uses the published fixed finite-program, actual-step-cost semantics and the existing binary instance encoding. The program and polynomial witnesses are chosen before the input. Output numbering is free only up to a bijection of variables and constraint occurrences preserving every ordered scope. Thus the machine must compute this exact finite gadget up to relabeling, rather than some other reduction. This is the left-hand side of Theorem C.15, defined independently of any minion homomorphism.

Definition code
import Mathlib
import Definitions.Def_AbelianPromises_Dichotomy_Complexity
import Definitions.Def_AbelianPromises_Dichotomy_Supplement_Gadget

set_option autoImplicit false

namespace AbelianPromises.Dichotomy.Supplement

/-- Numbering-independent representation of the same concrete finite instance.
Both variables (including isolated ones) and constraint occurrences are bijectively
renamed; every ordered scope, including repeated positions, must be preserved. -/
def InstanceIsomorphic (I J : Instance) : Prop :=
  ∃ (v : Fin I.n ≃ Fin J.n) (c : Fin I.m ≃ Fin J.m),
    ∀ (e : Fin I.m) (i : Fin 3), v (I.scope e i) = J.scope (c e) i

/-- Definition C.13 with the published bit-machine and promise semantics. The machine
must output a numbering of the specific concrete Phi gadget on every valid input.
Arbitrary quotient/Fintype numberings are not asserted to be computable: the machine
chooses a numbering, with exact finite-instance isomorphism as its representation test.
Its program and polynomial resource witnesses precede all instances in PolyComputable. -/
noncomputable def CSinglAIPReduction {A B C D : Type} [Fintype A] [Fintype C]
    (R : Relation A) (Q : Relation B) (S : Relation C) (T : Relation D) : Prop :=
  ∃ f : List Bool → List Bool, PolyComputable f ∧
    (∀ I : Instance, ∃ J : Instance,
      f (encodeInstance I) = encodeInstance J ∧ InstanceIsomorphic J (phi R S I)) ∧
    ReducesBy R Q S T f

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), Definition C.13, with the polynomial-time reduction convention of Section 2.

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