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.
In the paper
- page 5 of this submission's paper
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.