One exact polynomial-time RAM solver for rational linear programming
ProvedLax109476Proofs.RamUniformSolver.exists_exact_polynomial_time_solveralgorithmscomputational-complexitygraph-theory
There is one word-RAM algorithm , with polynomial bit-size resource bounds, that returns a valid exact certificate for every finite rational linear program:
The certificate describes an optimum, infeasibility or unboundedness. The algorithm also has bounded execution on arbitrary input words.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeSchemeInterfaces
Formal statement
theorem Lax109476Proofs.RamUniformSolver.exists_exact_polynomial_time_solver : ∃ (solve : List ℕ → List ℕ),
Lax759944.RamPolytime.RamPolytime solve ∧
∀ (m n : ℕ) (P : Lax109476.LinearProgram.Program ℚ m n),
∃ (certificate : Lax109476.RationalCertificates.Certificate m n),
solve (Lax109476.RationalEncoding.encodeProgram P) = Lax109476.RationalEncoding.encodeCertificate certificate ∧
Lax109476.RationalCertificates.IsValidCertificate P certificate := by sorrySource