Native exact LP execution for a canonical rational program
OpenLax109476Proofs.RamSolverCanonicalExecution.solve_specalgorithmscomputational-complexitygraph-theory
Let be a rational LP and the size of its canonical encoding. With and the published initialized source and workspace predicates, the actual solver command produces its complete certificate result within instructions:
This is a reusable source interface for composing the complete finite-program implementation.
Retired because the namespace-wrapped declaration compiled during publication but the proof-comparison parser rejects that header (expected token / unknown full theorem identifier). The mathematically identical, fully qualified declaration is Lax109476Proofs.RamSolverCanonicalExecution.solve_spec_native.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces
Formal statement
namespace Lax109476Proofs.RamSolverCanonicalExecution
theorem solve_spec : ∀ (m n w : Nat) (P : Lax109476.LinearProgram.Program Rat m n),
Nat.le
(Lax109476Proofs.RamUniformSolverBounds.wordWidth
(Lax759944.BinaryWordEncoding.bitSize (@Lax109476.RationalEncoding.encodeProgram m n P)))
w →
Lax808846Proofs.Reasoning.Spec
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
((2:Nat)) w)
(@Lax109476Proofs.RamSolverCanonicalExecution.Input m n
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
((2:Nat)) w)
P)
Lax109476Proofs.RamExactSolverProgram.solve (@Lax109476Proofs.RamSolverFinish.Result m n P)
(Lax109476Proofs.RamUniformSolverBounds.instructionBound
(Lax759944.BinaryWordEncoding.bitSize (@Lax109476.RationalEncoding.encodeProgram m n P))) := by sorry
end Lax109476Proofs.RamSolverCanonicalExecution
Source