Correctness and quadratic time bound of the pancake output stage
ProvedPancakeHard.ReductionCompiler.construct_stage_correctFix a valid unary CNF code with nonempty clauses of width at most three, an auxiliary input , a word width , and either output variant of the concrete RAM transducer. Write and assume
Starting at instruction 100 with the correctly parsed occurrence array, the shifted and padded literal array, and the decoded clause count, the program halts with the prescribed output within
steps, for every value of the scratch count, scratch literal, and tick counter. The output is the unary code of the canonical stack of Definition 8, with the breakpoint threshold prepended in the threshold variant.
This implementation lemma identifies the emitted variable, clause, dock, and lock blocks with the published stack definition and provides the running-time bound needed for the proof of Theorem 19.
import Mathlib import Definitions.Def_PancakeHard_ReductionProgram set_option autoImplicit false
namespace PancakeHard.ReductionCompiler
theorem construct_stage_correct {w : WordRAM.Width} {budget : Bool} (x y : List Bool)
(hroom : PancakeHard.ReductionCompiler.InputRoom x w) (hx : PancakeHard.ReductionProof.validInput x) :
∀ count value ticks, PancakeHard.ReductionCompiler.Reach budget (150000*(x.length+1)^2)
(PancakeHard.ReductionCompiler.PM (w := w) x y (8+x.length)
(PancakeHard.ReductionCompiler.arrOf (CookLevin.formulaN (CookLevin.decodeFormula x)) 0)
(PancakeHard.ReductionCompiler.padArrays (CookLevin.formulaN (CookLevin.decodeFormula x)))
(8+x.length+(PancakeHard.ReductionCompiler.arrOf (CookLevin.formulaN (CookLevin.decodeFormula x)) 0).length)
(CookLevin.decodeFormula x).length (CookLevin.decodeFormula x).length count value 100 ticks)
(PancakeHard.ReductionCompiler.Good budget x) := by sorry
end PancakeHard.ReductionCompiler