PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.CookLevin.Circuitization.GeneratorTransitionStatementAffineContextBranchRouteFamily
DefinitionPricingWithTips3DM_7056c2685e5712b969302baecomplexity-theorypricing-with-tipsthree-dimensional-matching
A private, kernel-checked dependency module used by the formal NP-hardness proof for three-dimensional matching and Theorems 4.1 and 4.2 of arXiv:2507.10872.
Definition code
import Definitions.Def_PricingWithTips3DM_958a644893103d57ea9b6b2a
import Definitions.Def_PricingWithTips3DM_645fa74d60687a6229a5303d
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false
/-!
# Typed raw-input row families for branch-ending statement results
The branch-route source emits one complete marked row per transition seed.
This module packages those rows behind the same typed family interface used
by normalized linear results.
-/
noncomputable section
namespace CLRS.Chapter34.Turing.CookLevin
open PolyBuilder
private theorem branchRoute_encodeUnaryFrame_frameEnd_free
(values : List Nat) :
∀ symbol ∈ encodeUnaryFrame values, symbol ≠ UnaryFrameSym.frameEnd := by
intro symbol hsymbol
induction values with
| nil => simp [encodeUnaryFrame] at hsymbol
| cons value values ih =>
simp only [encodeUnaryFrame, List.flatMap_cons] at hsymbol
rw [List.mem_append] at hsymbol
rcases hsymbol with hhead | htail
· unfold encodeUnaryFrameBlock at hhead
rw [List.mem_append] at hhead
rcases hhead with htick | hseparator
· have : symbol = UnaryFrameSym.tick :=
List.eq_of_mem_replicate htick
subst symbol
decide
· have : symbol = UnaryFrameSym.separator := by
simpa using hseparator
subst symbol
decide
· exact ih htail
/-- Semantic branch-route rows of one fixed statement context and mux
offset. -/
noncomputable def verifierTransitionStmtBranchRouteFamily
{Γ : Type} {L : Language Γ} (W : VerifierWitness L)
(labelOffset : TransitionAffineNat)
(context : TransitionStmtAffineContext W.machine.tm)
(offset : TransitionAffineNat)
(input : List Γ) : UnaryFrameMarkedRowFamily :=
{ rows := (verifierTransitionRowSeeds W input).map fun seed =>
encodeUnaryFrame
(transitionStmtBranchRouteValues W.machine.tm seed labelOffset
context offset)
frameEnd_free := by
intro row hrow symbol hsymbol
rw [List.mem_map] at hrow
rcases hrow with ⟨seed, hseed, rfl⟩
exact branchRoute_encodeUnaryFrame_frameEnd_free _ symbol hsymbol }
/-- The typed family encoding is exactly the concrete affine-segment source
stream. -/
theorem verifierTransitionStmtBranchRouteFamily_encoding_eq
{Γ : Type} {L : Language Γ} (W : VerifierWitness L)
(input : List Γ) (labelOffset : TransitionAffineNat)
(context : TransitionStmtAffineContext W.machine.tm)
(offset : TransitionAffineNat) :
encodeUnaryFrameMarkedRowFamily
(verifierTransitionStmtBranchRouteFamily W labelOffset context offset
input) =
verifierTransitionStmtBranchRouteFrames W labelOffset context offset
input := by
rw [verifierTransitionStmtBranchRouteFrames_eq]
unfold encodeUnaryFrameMarkedRowFamily
verifierTransitionStmtBranchRouteFamily
simp [List.flatMap_map]
/-- The typed semantic branch-route family is generated by a concrete fixed
polynomial-time TM2 from the original verifier word. -/
noncomputable def
verifierTransitionStmtBranchRouteFamily_computableInPolyTime
{Γ : Type} {L : Language Γ} (W : VerifierWitness L)
(labelOffset : TransitionAffineNat)
(context : TransitionStmtAffineContext W.machine.tm)
(offset : TransitionAffineNat) :
_root_.Turing.TM2ComputableInPolyTime id
encodeUnaryFrameMarkedRowFamily
(verifierTransitionStmtBranchRouteFamily W labelOffset context offset) := by
let source :=
verifierTransitionStmtBranchRouteFrames_computableInPolyTime W
labelOffset context offset
exact
{ tm := source.tm
inputAlphabet := source.inputAlphabet
outputAlphabet := source.outputAlphabet
time := source.time
outputsFun := fun input => by
simpa only [id_eq,
verifierTransitionStmtBranchRouteFamily_encoding_eq W input
labelOffset context offset] using source.outputsFun input }
end CLRS.Chapter34.Turing.CookLevin
Source