Proof of `The steps between objectives on words` (4th statement)

groundedproofs/Lax434175Proofs/ThresholdWords.lean · lax-434175

What this proof establishes

thm✓Lax434175.Operations
thm✓Lax434175.Propagation
thm✓Lax434175.ThresholdWords
thm✓Lax759944.TuringRamPolytimeEquivalence

thm✓Lax434175.ThresholdWords (4th statement)

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

Compose the reduction with the word map; its numbers grow at most polynomially.