PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.CookLevin.Circuitization.GeneratorValidityRowTailSource.Part2.Chunk4
DefinitionPricingWithTips3DM_bbaac3743d036b03526ad1a7Part2Chunk4complexity-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_bbaac3743d036b03526ad1a7Part2Chunk3
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false
noncomputable section
namespace CLRS.Chapter34.Turing.CookLevin
open PolyBuilder
/-- One normalized verifier row, typed for the payload-preserving affine
source. Its payload is exactly the compact one-hot source family already
computed by the seed-carrier normalization stage. -/
noncomputable def verifierValidityRowTailPayloadRows
{Γ : Type} {L : Language Γ} (W : VerifierWitness L)
(input : List Γ) : List AffineUnaryTriplePayloadRow :=
(verifierValidityRowSeeds W input).map fun seed =>
{ seed := validityRowAffineSeed seed.height seed.start seed.rowBase
payload := encodeAffineExactlyOneOutputSourceInvocationFamily
(validityRowSeedOneHotFrames W.machine.tm seed).reverse }
/-- Well-formed typed family presented to the generic affine source. -/
noncomputable def verifierValidityRowTailPayloadFamily
{Γ : Type} {L : Language Γ} (W : VerifierWitness L)
(input : List Γ) : AffineUnaryTriplePayloadFamily :=
{ rows := verifierValidityRowTailPayloadRows W input
payload_frameEnd_free := by
intro row hrow symbol hsymbol
rw [verifierValidityRowTailPayloadRows, List.mem_map] at hrow
rcases hrow with ⟨seed, hseed, rfl⟩
exact affineExactlyOneOutputInvocationFamily_no_frameEnd _ symbol hsymbol }
end CLRS.Chapter34.Turing.CookLevin
Source