Constraint singleton AIP pruning and kappa
DefinitionAbelianPromises_Dichotomy_Supplement_PruningOne CSinglAIP round tests the pinned AIP system for each currently surviving constraint tuple and deletes that tuple from its own constraint exactly when the test is infeasible. Repeating these rounds gives the fixed point. If is the initial total number of stored tuples, rounds suffice, since a nonstationary round deletes a tuple and tuples never return.
The construction then restricts each nonisolated variable domain to values compatible with every surviving incident constraint; isolated domains remain unchanged:
Rejection, including empty initial domains or relations, is represented separately and has no minion solution. Feasibility is specified by the actual signed integer equations, and no satisfying assignment, affine certificate, minion map, or oracle is an input. This construction supplies the concrete pruning operation used in the supplement.
Formalization Note Simultaneous deletion rounds implement the same greatest fixed point as exhaustive sequential deletions. The bound is a termination bound for this denotation, not an assumed polynomial-time integer-solving oracle.
import Mathlib
import Definitions.Def_AbelianPromises_Dichotomy_Supplement_CurrentCSP
set_option autoImplicit false
namespace AbelianPromises.Dichotomy.Supplement
/-- One simultaneous deletion round of Definition C.6. Feasibility is a mathematical
specification of integer-system solving, not a supplied oracle or certificate. -/
noncomputable def pruneRound (I : CurrentCSP) : CurrentCSP := by
classical
exact { I with tuples := fun c => (I.rel c).filter fun t => AIPFeasible (pinConstraint I c t) }
/-- There are at most this many strict tuple-deletion rounds. An extra round also covers
initial incompatible tuples. Empty constraints stay empty. -/
noncomputable def pruningFixedPoint (I : CurrentCSP) : CurrentCSP :=
(pruneRound^[1 + ∑ c, (I.tuples c).card]) I
/-- Retain all incident compatibility conditions; an isolated domain is unchanged. -/
def restrictDomains (I : CurrentCSP) : CurrentCSP :=
{ I with domain := fun x => (I.domain x).filter fun a =>
∀ (c : Fin I.m) (i : Fin (I.arity c)), I.scope c i = x →
∃ t ∈ I.rel c, t i = a }
/-- Kappa of Appendix C.3: run actual tuple pruning, then restrict domains. None denotes
rejection; in particular empty initial domains/relations are explicitly unsatisfiable. -/
noncomputable def kappa (I : CurrentCSP) : Option CurrentCSP := by
classical
let J := restrictDomains (pruningFixedPoint I)
exact if (∀ x, (J.domain x).Nonempty) ∧ (∀ c, (J.rel c).Nonempty) then some J else none
end AbelianPromises.Dichotomy.Supplement