Polynomial representation of the exact LP solver word-width bound
ProvedLax109476Proofs.RamUniformSolverBounds.width_polynomialalgorithmscomputational-complexitylinear-programming
Let be the fixed word-width bound of the complete exact rational LP solver on input encoding length . This function is exactly represented by a polynomial with natural coefficients:
The statement includes the decoder, certificate-decision, recovery and administrative width terms appearing in the published width formula. It is a resource bound for the single fixed solver program, uniform over every input length.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeCertificateInterfaces
Formal statement
theorem Lax109476Proofs.RamUniformSolverBounds.width_polynomial : Lax109476Proofs.RamResourcePolynomial.HasPolynomial Lax109476Proofs.RamUniformSolverBounds.wordWidth := by sorry
Source