The Cook composite computes finite source runs with linear overhead
ProvedCookPvsNP.comp_run_boundcompositionturing-machines
Suppose the first source halts on within steps and outputs , and the second halts on within steps and outputs , with ordinary word encodings. The original composite machine halts on the embedded and outputs the embedded at some time . All setup, translation, simulation, and cleanup transitions are included; the original machine and output convention are unchanged.
Preamble
import Definitions.Def_CookPvsNP_comp_machine
Formal statement
namespace CookPvsNP
theorem comp_run_bound {I S O A B : Type} [Fintype A] [Fintype B]
(ι : I ↪ A) (j₁ : S ↪ A) (j₂ : S ↪ B) (κ : O ↪ B)
(M₁ : TM A) (M₂ : TM B) (x : List I) (y : List S) (z : List O) (n₁ n₂ : ℕ)
(h₁ : M₁.HaltsWithin n₁ (x.map ι))
(o₁ : M₁.output (M₁.run n₁ (M₁.init (x.map ι))) = y.map (some ∘ j₁))
(h₂ : M₂.HaltsWithin n₂ (y.map j₂))
(o₂ : M₂.output (M₂.run n₂ (M₂.init (y.map j₂))) = z.map (some ∘ κ)) :
∃ t ≤ 20 * (x.length + n₁ + n₂ + 1),
(compTM j₁ j₂ M₁ M₂).HaltsWithin t (x.map (compInputEmbedding ι)) ∧
(compTM j₁ j₂ M₁ M₂).output
((compTM j₁ j₂ M₁ M₂).run t ((compTM j₁ j₂ M₁ M₂).init
(x.map (compInputEmbedding ι)))) = z.map (some ∘ compOutputEmbedding κ) := by sorry
end CookPvsNPSource
New auxiliary result derived from Sneed's exact published Prove2Me definition CookPvsNP_comp_machine, id 9c26b5f3-2f9d-4c5d-9194-692cbc786b4a (2026-09-30), without changing its transitions. It supports the existing CookPvsNP.tm_compose_poly_witness for the scheduling-hardness mission. The underlying one-tape machine model is Cook, The P versus NP problem, Clay Mathematics Institute (2000), Appendix. This particular representation and its equations are new formalization lemmas, not numbered claims of that paper.