Proof of `The Explicit Construction Runs in Polynomial Time`
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 output encoding is the rotation table of the selected tower member, with each row interpreted as one path-replacement vertex.
Proof strategy
Identify the numerical selector and bracket serialization with the proved polynomial-time tower-table construction. Transfer its deterministic machine through pointwise equality and the registered machine-model bridge.
Attribution
The zig-zag product is due to Reingold, Vadhan, and Wigderson. The tower-table and machine-model proofs are reused from the registered Lax323828 development, including contributions by Bolton Bailey and Samuel Schlesinger.