Polynomial finite-stack computations compile to Cook polynomial time
ProvedCookPvsNP.stack_polytimepolynomial-timeturing-machines
A fixed finite-control, finite-alphabet stack machine computing f on a designated output stack within |w|^k+k source steps witnesses CookPvsNP.PolyTimeComputable f. There is no requirement to clear other source stacks; the compiler performs that cleanup.
Preamble
import Definitions.Def_CookPvsNP_StackRepresentation
Formal statement
namespace CookPvsNP
theorem stack_polytime {K A Q : Type} [Fintype K] [Fintype A] [Fintype Q]
[DecidableEq K] [DecidableEq A] [DecidableEq Q]
(P : StackMachine K A Q) (ki ko : K) (f : List A → List A) (k : ℕ)
(h : ∀ w : List A, ∃ m, m ≤ w.length ^ k + k ∧
P.done ((P.step^[m]) (P.init ki w)).state = true ∧
((P.step^[m]) (P.init ki w)).store 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.