ram parse
ProvedResourceScheduling.Graph.ram_parsealgorithmspolynomial-time
The stack parser implements the exact unary-prefix state transformation in a linear number of source steps.
Preamble
import Definitions.Def_ResourceScheduling_Graph_RAMParse open CookPvsNP ResourceScheduling.Graph
Formal statement
namespace ResourceScheduling.Graph
theorem ram_parse {V : Type} [DecidableEq V] (t good : V) (hne : t ≠ good) :
StackImplements RAMRep (ramParse t good) (ramParseState t good)
(fun s => 3 * s.val t + 3 * s.val good + 3 * s.word.length + 7) := by sorry
end ResourceScheduling.GraphSource
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.