Cook-machine polynomial time for the concrete graph-to-Q2 word transformation
ProvedResourceScheduling.Graph.reduceWord_polyTimeLet be the published total graph-to-scheduling transformation: successfully parsed graph codes are sent to the original non-edge resource construction with speeds , and malformed words are sent to the empty word. The remaining computational obligation is that is computable by a Cook one-tape deterministic transducer in polynomial time. Precisely, there exist a finite work alphabet, injective input and output alphabet maps, one fixed machine , and one exponent such that for every word ,
The output equality uses the specified alphabet maps and the original convention of reading from the final head position and trimming trailing blanks. Semantic correctness and the quadratic output-size bound have been proved separately; this node isolates the outstanding machine construction and running-time proof.
import Definitions.Def_ResourceScheduling_Graph_WordReduction
namespace ResourceScheduling.Graph theorem reduceWord_polyTime : CookPvsNP.PolyTimeComputable reduceWord := by sorry end ResourceScheduling.Graph