Proof of `The Auxiliary Problem Reduces to Scheduling on Two Job Lengths` (3rd statement)

groundedproofs/Lax391470Proofs/L1Final.lean · lax-391470

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.

Read the Lean proof on GitHub

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.