apx_search
def
Pruned search over candidate seat vectors for a list of profiles; succeeds iff every complete assignment contains a population paradox.
Statement
def apx_search (done : List ((Fin 4 → ℕ) × (Fin 4 → ℕ)))
(todo : List ((Fin 4 → ℕ) × List (Fin 4 → ℕ))) : Bool- Source
- step towards quota_population_monotone_incompatible_four_states_common_house (common-house-size variant left open by arXiv:2608.02759, Sec. 5; cf. arXiv:2202.11061, Sec. 3.1)
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Built on 1
- apx_paradoxBoolean test for a population paradox between two four-state profiles with given seat vectors.
- Used by 2
- apx_search_soundIf the pruned search succeeds, every seat assignment choosing candidates for the profiles has a population paradox between two of them.
- apx_kernel_checkThe pruned search succeeds on the twelve profiles at house size 8 (kernel computation).
Lean source view module on GitHub
/-- Pruned search: assign each pending profile one of its candidate seat vectors; a branch is closed as soon as the new assignment forms a population paradox with an earlier one. Returns `true` iff every complete branch is closed. -/ def apx_search (done : List ((Fin 4 → ℕ) × (Fin 4 → ℕ))) (todo : List ((Fin 4 → ℕ) × List (Fin 4 → ℕ))) : Bool := match todo with | [] => false | (p, cs) :: rest => cs.all fun a => (done.any fun x => apx_paradox x.1 x.2 p a || apx_paradox p a x.1 x.2) || apx_search ((p, a) :: done) rest