Polynomial representation of the exact LP solver instruction bound
ProvedLax109476Proofs.RamUniformSolverBounds.cost_polynomialalgorithmscomputational-complexitylinear-programming
Let be the fixed instruction-bound function of the complete exact rational LP solver on input encoding length . There is a polynomial with natural coefficients representing it exactly:
The bound includes frontend execution, canonical-size administration, the selected certificate branch and final output. Combined with the operational solver specification, this representation supplies a uniform polynomial running-time bound for one finite deterministic program.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeCertificateInterfaces
Formal statement
theorem Lax109476Proofs.RamUniformSolverBounds.cost_polynomial : Lax109476Proofs.RamResourcePolynomial.HasPolynomial Lax109476Proofs.RamUniformSolverBounds.instructionBound := by sorry
Source