source budget
ProvedResourceScheduling.Graph.source_budgetalgorithmspolynomial-time
A structural register-program cost with a quadratic numeric bound, together with the linear output-transfer cost, is bounded by one Cook polynomial deadline for every input length.
Preamble
import Definitions.Def_CookPvsNP_defs
Formal statement
namespace ResourceScheduling.Graph
theorem source_budget (A d : ℕ) (hd : 2 ≤ d) : ∃ k, ∀ L c o : ℕ,
c ≤ A * (100 * (L + 1)^2 + 1)^d → o ≤ 5 * L^2 + 8 → c + 3 * o + 2 ≤ L^k + k := by sorry
end ResourceScheduling.GraphSource
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.