Proof of `Two polynomial-time conventions, and their separation` (1st statement)

groundedproofs/Lax560851Proofs/RamPolynomialComparison.lean · lax-560851

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

Description

The two input presentations define the same polynomial-time class for the full Lax808846 instruction set, including indexed input and EOF tests. The checked buffering compiler preserves the source input and output tapes; the internal legacy compilers then convert between the two presentations.

If TT and QQ are the source time and sufficient-width polynomials, the composed arena-to-native witnesses are 1188T+2382X+33821188*T + 2382*X + 3382 and Q+14Q + 14. The native-to-arena witnesses are 324T+108X+603324*T + 108*X + 603 and Q+14Q + 14. Both directions can introduce a linear startup term. Each implication chooses its own witnesses; no equality of polynomial degrees is stated or used.