Theorem 2, oracle step — Charged precomputation and reconstruction
ProvedFBMSP.oracle_operation_boundSuppose each nonempty index interval with has a declared oracle charge at most . For , summing these charges once over all nonempty intervals costs at most . Adding the declared Bellman candidate evaluations for additional layers and backtracking steps gives
The primitive oracle's charge includes both the optimal price and attained block revenue.
import Definitions.Def_FBMSP_DynamicProgram
namespace FBMSP
theorem oracle_operation_bound (n k m : ℕ) (hn : 1 ≤ n) (hk : 1 ≤ k)
(charge : ℕ → ℕ → ℕ)
(hCost : ∀ a b, a < b → b ≤ n → charge a b ≤ m) :
oracleCharges charge n ≤ m * blockOracleCalls n ∧
segmentationWork charge k n ≤ 5 * (n * n) * (k + m) := by sorry
end FBMSPRead-back
What the Lean code literally says, in plain math · gpt-6-astra
For all natural with and , and every function such that whenever , define and . The assertion is the conjunction and . Here has its ordinary value because , and the second left side is precisely the defined segmentation-work quantity: the sum of supplied nonempty-interval charges, times the triangular count through , and . The theorem imposes no bound on diagonal or out-of-range charges, which never enter the sum, and it does not quantify an oracle implementation or relate to execution time. The value is permitted and forces all the charged in-range entries to be zero; and are excluded.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.