A native polynomial-time rounded ellipsoid step
ProvedLax263307Proofs.NativeRoundedStep.exists_programalgorithmscomputational-complexitygraph-theory
One fixed RAM program performs the rational rounded ellipsoid update. There is a positive constant such that valid dimension- states, integer separating normals, and height parameter satisfy
for the actual instruction count and sufficient host word width. The output is the exact prescribed rounded update, including both center and shape matrix.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeSchemeInterfaces
Formal statement
theorem Lax263307Proofs.NativeRoundedStep.exists_program : ∃ (p : Lax808846.Ram.Program) (c : ℕ),
0 < c ∧
∀ (n k h : ℕ),
2 ≤ n →
1 ≤ h →
∀ (state : Lax263307.RoundedOracleSearch.State n) (a : Fin n → ℤ),
(∀ (i j : Fin n), Lax263307.NativeRoundedStep.height (state.1 i j) h) →
(∀ (i : Fin n), Lax263307.NativeRoundedStep.height (Lax263307.RoundedOracleSearch.rationalNormal a i) h) →
(∀ (i : Fin n), Lax263307.NativeRoundedStep.height (state.2 i) h) →
0 <
Lax263307.RoundedOracleSearch.rationalNormal a ⬝ᵥ
state.1.mulVec (Lax263307.RoundedOracleSearch.rationalNormal a) →
∀ (w : ℕ),
c * (n + h + k + 1) ^ 12 ≤ w →
∃ t ≤ c * (n + h + k + 1) ^ 12,
Lax808846.Ram.RunsTo w p (Lax263307.NativeRoundedStep.encodeInput k state a)
(Lax263307.NativeRoundedStep.encodeOutput (Lax263307.RoundedOracleSearch.update k state a))
t := by sorrySource