While this submission is a draft, it cannot be used by other submissions.

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 program on the length-prefixed word is a polynomial-time word RAM computation of the decision on the zeros and ones of the word, with all values polynomially bounded; the RAM/Turing equivalence of lax−759944lax-759944 and the two translations of lax−391470lax-391470 give a polynomial-time Turing machine on the binary word, and a machine writing the one bit of the answer is a machine for the class.