Proof of `Two polynomial-time conventions, and their separation` (1st statement)
groundedproofs/Lax560851Proofs/RamPolynomialComparison.lean · lax-560851
What this proof establishes
no assumptions
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 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 and are the source time and sufficient-width polynomials, the composed arena-to-native witnesses are and . The native-to-arena witnesses are and . Both directions can introduce a linear startup term. Each implication chooses its own witnesses; no equality of polynomial degrees is stated or used.