AFTD Auto-Formalizing Theoretical Domains

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
See it in the graphDiscuss this resultChallenge it