Polynomial-bit optimization of clique factors by exact output count
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.bounded_width_factor_optimizeralgorithmsclusteringdynamic-programming
For fixed width, optimize explicitly enumerable finite-domain variables with polynomially evaluable clique factors. A factor emits a finite list of items. At each attainable total item count, retain an actual output attaining minimum additive rational cost. The factor graph and a tree decomposition can be recovered from the enumerated scopes for fixed width. The statement is independent of clustering.
Preamble
import Definitions.Def_QuantumMaxCutFiniteNumericRuntime import Definitions.Def_StableMSR_Recovery_Supplement_CliqueFactors open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open OAI.MetricKMedian.Binary.Automatic
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.bounded_width_factor_optimizer {α : Type} [Coding α] [Inhabited α] (t : ℕ)
(vars terms : α→Block) (dom : α→List Value) (scope : α×ℕ→Block)
(emit : (α×ℕ)×Plan→Pack) (cost : α×Block→ℚ)
(p1 : Poly vars) (p2 : Poly terms) (p3 : Poly dom) (p4 : Poly scope)
(p5 : Poly emit) (p6 : Poly cost) :
∃ F : α→Table, Poly F ∧ ∀ a,
ScopeWidth (vars a) ((terms a).map (fun i => scope (a,i))) t →
(∀ i∈terms a, DependsOn (vars a) (scope (a,i)) (fun s => emit ((a,i),s))) →
FactorRow (vars a) (dom a) (renderFactors (terms a) (fun i s => emit ((a,i),s)))
(fun w => cost (a,w)) (F a) := by
sorry
Source
Finite-domain bounded-treewidth optimization with exact cardinalities and witnesses. See Ravichandran and Reyzin, Appendix A.6 (https://arxiv.org/abs/2611.03547) and Freuder, Complexity of k-tree structured constraint satisfaction problems, AAAI 1990.