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.
Description
The two halves of the paper's Section 4. From a satisfying assignment, 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 reads the assignment off a schedule. 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 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.