op75_tm2_poly_output_size
theoremverified
Every function computed by a polynomial-time TM2 has output encoding length bounded by a polynomial in its input encoding length.
Statement
theorem op75_tm2_poly_output_size {α β αΓ βΓ : Type} {ea : α → List αΓ} {eb : β → List βΓ} {f : α → β} (M : Turing.TM2ComputableInPolyTime ea eb f) : ∃ q : Polynomial ℕ, ∀ a, (eb (f a)).length ≤ q.eval (ea a).length
- Source
- OP-75: polynomial output-size bound needed for composing Karp reductions.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- op75_tm2_output_linear_boundFor any finite TM2, there is a constant C such that for every input and output, a halting run of at most n steps has output length at most…
- Used by 2
- op75_tm2_inhabited_compPolynomial-time finite stack machines compose whenever their intermediate alphabet is inhabited; the input and output alphabets are…
- op75_tm2_bool_compPolynomial-time finite stack machines compose when their intermediate alphabet is Boolean, for arbitrary input and output alphabets.
Lean source view module on GitHub
theorem op75_tm2_poly_output_size {α β αΓ βΓ : Type} {ea : α → List αΓ} {eb : β → List βΓ} {f : α → β} (M : Turing.TM2ComputableInPolyTime ea eb f) : ∃ q : Polynomial ℕ, ∀ a, (eb (f a)).length ≤ q.eval (ea a).length := by obtain ⟨C, hC⟩ := op75_tm2_output_linear_bound M.tm refine ⟨Polynomial.X + Polynomial.C C * M.time, ?_⟩ intro a have h := hC (List.map M.inputAlphabet.invFun (ea a)) (List.map M.outputAlphabet.invFun (eb (f a))) (M.time.eval (ea a).length) ⟨M.outputsFun a⟩ simpa using h