Lemma 5.8 (used in the proof of Theorem 1.3) — general terminal-algorithm combination
OpenFasterExactColoring.ThreeColor.Supplement.terminal_algorithm_combinationFix , , weights satisfying all of Appendix D, arbitrary finite parameter and algorithm counts , fixed matrices and , and a polynomial-time computable nonnegative vector for each valid terminal restricted instance. Assume
For each row , assume one actual uniform terminal algorithm with time , where is the original input order. Let satisfy
componentwise. Then one uniform finite program decides four-colorability of every graph in time
If the finite portfolio is deterministic, so is the resulting program. If its algorithms are one-sided Monte Carlo, the program has success at least on yes-instances, never accepts no-instances, and has charged worst-case time on every tape. All needed amplification is included. Constants can depend on the fixed weights, matrices, parameter routine and finite portfolio, but never on a graph or its order. The conclusion is algorithm existence, not just the dual scalar inequality. It is not restricted to the eleven-parameter application.
Differences from the source:
- encoding: polynomial-time computable nonnegative real parameter vectors → one deterministic finite program computes dyadic approximations to error 2^(-q) in time polynomial in n+q+1; reason: an explicit precision interface represents real-valued computation without an uncharged exact-real oracle; all finite exact source parameter vectors admit this representation
- generalization: deterministic terminal algorithms → the composition is stated in deterministic and one-sided Monte Carlo modes; reason: the deterministic specialization is the printed lemma; the randomized extension is the same composition used in the source Theorem 1.4 application, charging independent amplification
import Mathlib import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_Portfolio set_option autoImplicit false
namespace FasterExactColoring.ThreeColor.Supplement
theorem terminal_algorithm_combination (mode : Mode) {p a : ℕ}
(γ r : ℝ) (w : Weights) (M : Matrix (Fin 3) (Fin p) ℝ)
(R : Matrix (Fin a) (Fin p) ℝ) (x : {n : ℕ} → Restricted n → Fin p → ℝ)
(η : Fin a → ℝ) (hγ : 0 ≤ γ) (hr : 1 < r) (hw : appendixD r w)
(hcompute : parametersComputable x) (hx : parameterIdentity x M)
(hportfolio : terminalPortfolio mode γ x R) (hdual : dualComparison r w M R η) :
∃ (A : Program) (C : ℝ) (d : ℕ), 0 < C ∧
graphSolver mode 4 A C d (r*Real.exp γ) := by sorry
end FasterExactColoring.ThreeColor.Supplement