While this submission is a draft, it cannot be used by other submissions.

Proof of `The scheduling problems, parameterized`

groundedproofs/Lax470956Proofs/Pmax.lean · lax-470956

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

Description

The program reads the two header entries, then the nn processing times, keeping the largest seen, and writes it. The loop costs 1515 per entry and the whole command 1212 more, and the compiler charges 1010 machine instructions per unit of that cost plus a final halthalt, so 151(x+1)151 · (|x| + 1) covers it.

The domain is the submission's standard fitting condition rather than a bound on the sum of the word: the value bound the IMP+ program needs is the length of the word plus its largest entry, which one entry's fitting condition already supplies.