Nested composition budgets fit one Cook exponent
ProvedCookPvsNP.comp_budgetcompositionturing-machines
For any natural source exponents , there is a single natural exponent such that, for every input length , the quantity is at most . The estimate includes lengths zero and one and zero exponents.
Preamble
import Definitions.Def_CookPvsNP_defs
Formal statement
namespace CookPvsNP
theorem comp_budget (k₁ k₂ : ℕ) : ∃ k, ∀ n : ℕ,
20 * (n + (n ^ k₁ + k₁) + ((n + (n ^ k₁ + k₁) + 1) ^ k₂ + k₂) + 1) ≤
n ^ k + k := 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.