Tight-block recognition and witness tables have polynomial binary programs
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.tight_block_policy_programsalgorithmsclusteringdynamic-programming
For each fixed width, the full witness table and Boolean decision are polynomial-time bit programs. All loops are bounded by input lists and each recursive table is a filtered sublist of a precomputed polynomial-size pool.
Preamble
import Definitions.Def_QuantumMaxCutFiniteNumericRuntime import Definitions.Def_StableMSR_Recovery_Supplement_TightBlockPolicies open StableMSR.Recovery StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch open StableMSR.Recovery.DecompositionSearch RobertsonSeymour1986.GM5 open OAI.MetricKMedian.Binary.Automatic
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.tight_block_policy_programs (t : ℕ) : Poly (policy t) ∧ Poly (decideWidth t) := by sorry
Source
Constructive binary implementation of the tight-block recurrence in StableMSR.Recovery.DecompositionSearch.finite_decomposition_search, https://prove2.me/theorems/d4f2a14a-b18f-44f7-966a-d1411797cf17.