AND of two poly-time deciders is a poly-time decider: relocate clobbered witness tape between runs, stay polynomial
ProvedCookLevin.boundedExpr_and_machineComposition-kit lemma for the CLIQUE Cook-Levin lane: AND-combination of polynomial-time deciders. If well-formed machines M1 and M2 decide Boolean verdicts V1 and V2 within polynomial bounds polyBound c1 d1 and polyBound c2 d2, then there exists a well-formed machine M deciding the conjunction fun x y => (V1 x y) && (V2 x y) within a polynomial bound polyBound c d. The machine runs M1 on (x, y), stashes M1's verdict bit, relocates the witness tape (M1 may have clobbered it — the relocation is explicit in the construction; no naive monotonicity on the clobbered tape is claimed), runs M2 on the restored (x, y), and reports the AND of the two verdict bits. The composite constants c, d absorb the stash/relocation overhead as well as M2's bound at the restored witness input. This is the AND-combination primitive used to assemble per-constructor machines for CookLevin.BoundedExpr evaluation from sub-expression machines (e.g. the short-circuit conjunction both).
import Definitions.Def_CookLevin_Cost import Definitions.Def_CookLevin_BoundedExpr
namespace CookLevin
/-- Composition-kit child 2/3 (AND-combine): the AND of two poly-time
deciders is a poly-time decider. The witness tape is relocated between
the two runs (M1 may clobber it); the existential composite constants
absorb the relocation overhead. -/
theorem boundedExpr_and_machine
(V1 V2 : 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))
(V1 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))
(V2 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))
((V1 x y) && (V2 x y)) := by
sorry
end CookLevin