stack bounded loop
ProvedCookPvsNP.stack_bounded_loopalgorithmspolynomial-time
A loop with n certified body executions, correct guards, and body cost at most B executes in at most n(B+2)+1 source steps.
Preamble
import Definitions.Def_CookPvsNP_StackProgram open CookPvsNP
Formal statement
namespace CookPvsNP
theorem stack_bounded_loop {K A : Type} (test : (K → Option A) → Bool) (p : StackProg K A)
(n : ℕ) (s : ℕ → K → List A) (cost : ℕ → ℕ) (B : ℕ)
(hg : ∀ i < n, test (fun k => (s i k).head?) = true)
(he : test (fun k => (s n k).head?) = false)
(hb : ∀ i < n, p.Exec (s i) (s (i + 1)) (cost i))
(hc : ∀ i < n, cost i ≤ B) :
∃ t ≤ n * (B + 2) + 1, (StackProg.loop test p).Exec (s 0) (s n) t := by sorry
end CookPvsNPSource
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.