PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.CookLevin.Circuitization.GeneratorTransitionStatementAffineContextRecursiveBranchSelectorSource
DefinitionPricingWithTips3DM_640fcf3124410168551fb79bcomplexity-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_df98090fb2416a1cef91beb0
import Definitions.Def_PricingWithTips3DM_6cb06fb79c6a3de63bb3e159
import Definitions.Def_PricingWithTips3DM_645fa74d60687a6229a5303d
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false
/-!
# Raw-input selector rows for recursive branch muxes
The selector of a fixed recursive branch is one affine wire form evaluated at
each transition seed. A singleton affine segment therefore emits exactly
one marked singleton row per seed and supplies a concrete polynomial-time
source for the first channel of the four-row mux packet.
-/
noncomputable section
namespace CLRS.Chapter34.Turing.CookLevin
open PolyBuilder
/-- Singleton segment carrying the branch predicate-result wire. -/
def transitionStmtRecursiveBranchSelectorSegment
(tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
(context : TransitionStmtAffineContext tm) (test : tm.σ → Bool) :
TransitionWidenedFallbackSegment :=
{ base := transitionStmtBranchSelectorForm tm labelOffset context test
step := 0
count := TransitionAffineNat.const 1 }
/-- The selector segment evaluates to the canonical singleton selector row. -/
theorem transitionStmtRecursiveBranchSelectorSegment_values
(tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
(labelOffset : TransitionAffineNat)
(context : TransitionStmtAffineContext tm) (test : tm.σ → Bool) :
transitionWidenedFallbackSegmentValues seed
(transitionStmtRecursiveBranchSelectorSegment tm labelOffset context
test) =
[affineUnaryTripleFormValue
(transitionStmtBranchSelectorForm tm labelOffset context test)
(transitionTailAffineSeed seed)] := by
rw [transitionWidenedFallbackSegmentValues_eq_ofFn]
simp [transitionStmtRecursiveBranchSelectorSegment]
private theorem recursiveBranchSelector_encodeUnaryFrame_frameEnd_free
(values : List Nat) :
∀ symbol ∈ encodeUnaryFrame values, symbol ≠ UnaryFrameSym.frameEnd := by
intro symbol hsymbol
rw [encodeUnaryFrame, List.mem_flatMap] at hsymbol
rcases hsymbol with ⟨value, _, hblock⟩
simp [encodeUnaryFrameBlock] at hblock
rcases hblock with ⟨_, rfl⟩ | rfl <;> simp
/-- One marked singleton selector row per transition seed. -/
noncomputable def verifierTransitionRecursiveBranchSelectorFamily
{Γ : Type} {L : Language Γ} (W : VerifierWitness L)
(labelOffset : TransitionAffineNat)
(context : TransitionStmtAffineContext W.machine.tm)
(test : W.machine.tm.σ → Bool)
(input : List Γ) : UnaryFrameMarkedRowFamily :=
{ rows := (verifierTransitionRowSeeds W input).map fun seed =>
encodeUnaryFrame
[affineUnaryTripleFormValue
(transitionStmtBranchSelectorForm W.machine.tm labelOffset context
test)
(transitionTailAffineSeed seed)]
frameEnd_free := by
intro row hrow symbol hsymbol
rw [List.mem_map] at hrow
rcases hrow with ⟨seed, hseed, rfl⟩
exact recursiveBranchSelector_encodeUnaryFrame_frameEnd_free _ symbol
hsymbol }
/-- The typed selector family is exactly the singleton affine-segment
source. -/
theorem verifierTransitionRecursiveBranchSelectorFamily_encoding_eq
{Γ : Type} {L : Language Γ} (W : VerifierWitness L)
(input : List Γ) (labelOffset : TransitionAffineNat)
(context : TransitionStmtAffineContext W.machine.tm)
(test : W.machine.tm.σ → Bool) :
encodeUnaryFrameMarkedRowFamily
(verifierTransitionRecursiveBranchSelectorFamily W labelOffset context
test input) =
verifierTransitionAffineSegmentRowFrames W
[transitionStmtRecursiveBranchSelectorSegment W.machine.tm labelOffset
context test] input := by
rw [verifierTransitionAffineSegmentRowFrames_eq]
unfold encodeUnaryFrameMarkedRowFamily
verifierTransitionRecursiveBranchSelectorFamily
encodeUnaryFrameFixedGroupPrefixDropInput
transitionAffineSegmentValueRows
simp only [List.flatMap_map, List.map_cons, List.map_nil,
List.flatMap_cons, List.flatMap_nil]
apply List.flatMap_congr
intro seed hseed
rw [transitionStmtRecursiveBranchSelectorSegment_values]
simp
/-- The recursive branch selector channel is generated by a concrete fixed
polynomial-time TM2 from the raw verifier input. -/
noncomputable def
verifierTransitionRecursiveBranchSelectorFamily_computableInPolyTime
{Γ : Type} {L : Language Γ} (W : VerifierWitness L)
(labelOffset : TransitionAffineNat)
(context : TransitionStmtAffineContext W.machine.tm)
(test : W.machine.tm.σ → Bool) :
_root_.Turing.TM2ComputableInPolyTime id
encodeUnaryFrameMarkedRowFamily
(verifierTransitionRecursiveBranchSelectorFamily W labelOffset context
test) := by
let source := verifierTransitionAffineSegmentRowFrames_computableInPolyTime W
[transitionStmtRecursiveBranchSelectorSegment W.machine.tm labelOffset
context test]
exact
{ tm := source.tm
inputAlphabet := source.inputAlphabet
outputAlphabet := source.outputAlphabet
time := source.time
outputsFun := fun input => by
simpa only [id_eq,
verifierTransitionRecursiveBranchSelectorFamily_encoding_eq W input
labelOffset context test] using source.outputsFun input }
end CLRS.Chapter34.Turing.CookLevin
Source