seq-compose of two poly-time deciders: relocate M1's verdict to M2's witness tape, stay polynomial
ProvedCookLevin.boundedExpr_seqCompose_machineComposition-kit lemma for the CLIQUE Cook-Levin lane: sequential composition of polynomial-time deciders. If well-formed machines M1 and M2 decide Boolean relations R1 and R2 within polynomial bounds polyBound c1 d1 and polyBound c2 d2, then there exists a well-formed machine M deciding the sequenced relation fun x y => R2 x [R1 x y] within a polynomial bound polyBound c d. The machine runs M1 on (x, y), relocates M1's verdict bit onto M2's witness tape, runs M2, and reports M2's verdict. The composite constants c, d absorb the copy/relocation overhead as well as M2's bound at its length-1 witness input. This is the sequencing primitive used to assemble per-constructor machines for CookLevin.BoundedExpr evaluation from sub-expression machines.
import Definitions.Def_CookLevin_Cost import Definitions.Def_CookLevin_BoundedExpr
namespace CookLevin
/-- Composition-kit child 1/3 (sequencing): sequencing two poly-time
deciders through a witness-tape relocation stays poly-time. -/
theorem boundedExpr_seqCompose_machine
(R1 R2 : List Bool → List Bool → Bool)
(M1 M2 : CookLevin.Machine)
(k1 k2 G1 G2 c1 d1 c2 d2 : Nat)
(hwf1 : CookLevin.TuringMachine k1 G1 M1)
(hdec1 : ∀ (x y : List Bool),
CookLevin.DecidesIn M1 k1
(CookLevin.boolsToSymbols x) (CookLevin.boolsToSymbols y)
(CookLevin.polyBound c1 d1 (x.length + y.length))
(R1 x y))
(hwf2 : CookLevin.TuringMachine k2 G2 M2)
(hdec2 : ∀ (x w : List Bool),
CookLevin.DecidesIn M2 k2
(CookLevin.boolsToSymbols x) (CookLevin.boolsToSymbols w)
(CookLevin.polyBound c2 d2 (x.length + w.length))
(R2 x w)) :
∃ (M : CookLevin.Machine) (k G c d : Nat),
CookLevin.TuringMachine k G M ∧
∀ (x y : List Bool),
CookLevin.DecidesIn M k
(CookLevin.boolsToSymbols x) (CookLevin.boolsToSymbols y)
(CookLevin.polyBound c d (x.length + y.length))
(R2 x [R1 x y]) := by
sorry
end CookLevin