Proof of `Corollary 2`

groundedproofs/Lax496464Proofs/Ram/D4Final.lean · lax-496464

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

In the paper

  • page 4 of this submission's paper

Description

Corollary 2 as a word RAM program. Read the word, sort the jobs by start time, sum the preprocessing times into PP, and fill the dual table of Section 3 over sets of thresholds written as base-(n+1)(n+1) numbers: the numbers are visited from the top, each is decided to be a code of a set or not by a recurrence, and the two sets X1X₁, X2X₂ of recursion (1) are found by one scan of its digits (O(∣X∣)O(|X|), independent of PP), after which its P+1P+1 cells cost O(1)O(1) each. The table records, for each instant t=0…Pt = 0 … P, the largest weight attainable from tt, capped at the threshold (so its entries never leave the word); the block of the empty set is zero, and the answer is the entry of the first mm indices at instant 00. The sets contribute Σ(∣X∣+1)≤2(n+1)mΣ(|X|+1) ≤ 2 (n+1)^m in all. The domain restricts to positive processing times, the paper's standing assumption for Lemma 1's recursion. The running time is c(P+1)(n+1)m+c⋅sortCostc (P+1) (n+1)^m + c · sortCost: no work per machine beyond the O(∣X∣)O(|X|) scan of a set.