PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.CookLevin.Circuitization.GeneratorValidityRowTailSource.Part2.Chunk5
DefinitionPricingWithTips3DM_bbaac3743d036b03526ad1a7Part2Chunk5complexity-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_bbaac3743d036b03526ad1a7Part2Chunk4
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false
noncomputable section
namespace CLRS.Chapter34.Turing.CookLevin
open PolyBuilder
/-- The normalized seed-first byte stream is definitionally the concrete
encoding of the typed payload family. -/
theorem verifierValidityRowTailPayloadFamily_encoding_eq
{Γ : Type} {L : Language Γ} (W : VerifierWitness L)
(input : List Γ) :
encodeAffineUnaryTriplePayloadFamily
(verifierValidityRowTailPayloadFamily W input) =
verifierValidityRowSeedFirstOutputInvocationFrames W input := by
rw [verifierValidityRowSeedFirstOutputInvocationFrames_eq_rows]
unfold encodeAffineUnaryTriplePayloadFamily
change encodeAffineUnaryTriplePayloadRowFamily
(verifierValidityRowTailPayloadRows W input) = _
unfold verifierValidityRowTailPayloadRows
generalize verifierValidityRowSeeds W input = seeds
induction seeds with
| nil => rfl
| cons seed rest ih =>
simp only [List.map_cons, encodeAffineUnaryTriplePayloadRowFamily,
List.flatMap_cons]
rw [ih]
simp [encodeAffineUnaryTriplePayloadRow,
encodeAffineUnaryTripleSeed,
encodeAffineExactlyOneStructuredRowSeed, validityRowAffineSeed,
List.append_assoc]
end CLRS.Chapter34.Turing.CookLevin
Source