Proof of `The auxiliary problem reduces to scheduling on two job lengths` (3rd statement)
What this proof establishes
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 reduction is a word RAM program on the zeros and ones of its input: a one-pass tokenizer decodes the instance of the auxiliary problem, a second pass checks the conditions on its deadlines, and a printer writes the binary codes of the jobs of the stacked instance, signs included. Decoded numbers may be exponential in the length of the input, which the word length of a polynomial-time word RAM accommodates. Polynomial time on the word RAM transfers to a Turing machine.