stack trace laws
ProvedCookPvsNP.stack_trace_lawsalgorithmspolynomial-time
Stack traces compose, map along a step-preserving nonhalting configuration map, and imply the corresponding machine iterate.
Preamble
import Definitions.Def_CookPvsNP_StackProgram open CookPvsNP
Formal statement
namespace CookPvsNP
theorem stack_trace_laws {K A Q : Type} (P : StackMachine K A Q) :
(∀ {n : ℕ} {c d : StackCfg K A Q}, StackTrace P n c d → (P.step^[n]) c = d) ∧
(∀ {n m : ℕ} {c d e : StackCfg K A Q}, StackTrace P n c d → StackTrace P m d e →
StackTrace P (n + m) c e) ∧
(∀ {R : Type} (S : StackMachine K A R) (f : StackCfg K A Q → StackCfg K A R),
(∀ c, P.done c.state = false → S.done (f c).state = false ∧ S.step (f c) = f (P.step c)) →
∀ {n : ℕ} {c d : StackCfg K A Q}, StackTrace P n c d → StackTrace S n (f c) (f d)) := 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.