The specified CSinglAIP reduction with machine semantics
DefinitionAbelianPromises_Dichotomy_Supplement_ReductionThe relation means that the specific transformation is a polynomial-time promise reduction. Its machine must output a representation of the concrete for every encoded input instance, send every -satisfiable instance to an -satisfiable one, and send every instance without a -solution to one without a -solution:
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.
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