Theorem 2, counting step — Quadratic table bound
ProvedFBMSP.dp_operation_boundFor , additional Bellman layers, and charge per nonempty interval oracle call, the specified table-operation count satisfies
Here the paper's price budget corresponds to . This counts a memoized bottom-up schedule, not recursive recomputation. A complete proof of this generic count has been checked locally.
import Definitions.Def_FBMSP_DynamicProgram
namespace FBMSP
theorem dp_operation_bound (k n m : ℕ) (hn : 1 ≤ n) :
tableWork k n m ≤ 4 * (n * n) * (k + m) := by sorry
end FBMSPRead-back
What the Lean code literally says, in plain math · gpt-6-astra
For all natural numbers with , define , , and . The assertion is , or equivalently . Thus the left side charges for each of entries and adds candidate counts. The theorem is an inequality about these defined natural numbers and does not quantify over an implementation or establish a relation to a machine's running time. Both and are allowed, including their simultaneous zero case; is excluded.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.