stack map transfer
ProvedCookPvsNP.stack_map_transferalgorithmspolynomial-time
Mapped transfer has the exact transformed store and the same linear step count as ordinary transfer.
Preamble
import Definitions.Def_CookPvsNP_StackMapTransfer open CookPvsNP
Formal statement
namespace CookPvsNP
theorem stack_map_transfer {K A : Type} [DecidableEq K] (src : K) (targets : K → Bool) (f : A → A)
(s : K → List A) :
(mapTransferProg src targets f).Exec s (mapTransferStore src targets f s) (3 * (s src).length + 1) := 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.