polynomial absorb
ProvedCookPvsNP.polynomial_absorbalgorithmspolynomial-time
Every fixed natural polynomial coefficient and additive constant can be absorbed into a single bound n to the k plus k, including inputs of length zero and one.
Preamble
import Definitions.Def_CookPvsNP_defs
Formal statement
namespace CookPvsNP theorem polynomial_absorb (A d B : ℕ) : ∃ k, ∀ n : ℕ, A * (n + 1) ^ d + B ≤ n ^ k + k := by sorry end CookPvsNP
Source
New auxiliary formalization for the ResourceScheduling Q2 reduction. The target is the unchanged CookPvsNP one-tape machine model, following Cook, The P versus NP problem, Clay Mathematics Institute (2000), Appendix. This explicit finite-column stack compiler and its simulation lemmas are new contributions, not numbered claims from Cook or the scheduling source paper.