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

Proof of `Construction 2` (1st statement)

groundedproofs/Lax470956Proofs/Construction2.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 two halves of the paper's Section 4. From a satisfying assignment, lemma3lemma3 builds the schedule: each variable job goes on the machine opposing its value, freeing the agreeing machine for the selected literal of every clause that variable satisfies, and the remaining jobs of a clause are distributed over its own three machines by the transposition exchanging the selected literal with the first.

Conversely lemma4lemma4 reads the assignment off a schedule. observation4observation4 first shows that the two wrapper jobs of each literal share a machine — all three wrappers of one side pairwise overlap, so they are spread bijectively over the clause's machines, and the evenness of the deadlines forces that bijection to be the identity. Machine 00 of the clause is then blocked for two literals, and the third literal job has nowhere to go but its variable machine, which pins the variable job to the opposite one.