A quadratic size bound for the unary graph-to-Q2 encoding
ProvedResourceScheduling.Graph.q2_construct_encoding_length_leencodingpolynomial-boundscheduling
Let be a graph on vertices, encoded as unary followed by its adjacency matrix, and let be the length of this graph code. Apply the mission's non-edge resource construction, use speeds and , and threshold . The exact unary code of the resulting scheduling instance satisfies
The bound includes and uses the existing encodings without modification. It supplies an output-size estimate for the subsequent Turing-machine implementation; a running-time bound is a separate obligation.
Preamble
import Definitions.Def_ResourceScheduling_Graph_Construction
Formal statement
namespace ResourceScheduling.Graph
theorem q2_construct_encoding_length_le (d : GraphData) :
(encQ2 (![2, 1], reduce d)).length ≤ 5 * (encGraph d).length ^ 2 + 8 := by sorry
end ResourceScheduling.GraphSource
New elementary encoding lemma for the exact Prove2Me ResourceScheduling.Graph encodings (ResourceScheduling_Graph_Complexity, ResourceScheduling_Graph_GraphPartition, ResourceScheduling_Graph_ResDot11, ResourceScheduling_Graph_Construction). Construction: Blazewicz, Lenstra and Rinnooy Kan, Discrete Applied Mathematics 5 (1983), p. 15, Theorems 2-3, https://doi.org/10.1016/0166-218X(83)90012-4; author preprint https://ir.cwi.nl/pub/9642/9642D.pdf, printed pp. 5-6. The numerical encoding bound and parser lemmas are auxiliary results for the platform encoding, not numbered claims of the paper.