stack program polytime
ProvedCookPvsNP.stack_program_polytimealgorithmspolynomial-time
Polynomially bounded executions of a fixed structured stack program imply Cook polynomial-time computability of its designated output.
Preamble
import Definitions.Def_CookPvsNP_StackProgram open CookPvsNP
Formal statement
namespace CookPvsNP
theorem stack_program_polytime {K A : Type} [Fintype K] [Fintype A] [DecidableEq K] [DecidableEq A]
(p : StackProg K A) (ki ko : K) (f : List A → List A) (k : ℕ)
(h : ∀ w : List A, ∃ s n, n ≤ w.length ^ k + k ∧
p.Exec (fun j => if j = ki then w else []) s n ∧ s ko = f w) :
PolyTimeComputable f := 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.