Proof of `The Auxiliary Problem Is NP-Complete` (5th 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 finite-state scan decodes the formula, the numbers of the constructed instance are computed into arrays, and a printer writes their binary codes. Polynomial time on the word RAM transfers to a Turing machine.