PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.GeneralClique.OccurrenceReduction.Machine.CompatibilityEdgesPriorRows.Part1
DefinitionPricingWithTips3DM_0e75ff46933231ddbfe3b079Part1complexity-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_587002a90801ede7195efef5
import Mathlib.Tactic
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false
/-!
# Occurrence compatibility edges: all prior rows
This file iterates the verified one-row scan across the complete family below
one current occurrence. The resulting reversed rows carry their exact
compatibility tags and the controller reaches the counter-cleanup boundary.
-/
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false
noncomputable section
open StateTransition
namespace CLRS
namespace Chapter34
namespace Turing
namespace TMClique
open PolyBuilder
/-- One reversed prior row together with its compatibility tag. -/
def encodeTaggedOccurrenceEntry
(current prior : IndexedOccurrence × Nat) : List UnaryFrameSym :=
encodeCompatibilityTag (indexedOccurrencesCompatibleCode current prior) ++
(encodeIndexedOccurrenceEntry prior).reverse
end TMClique
end Turing
end Chapter34
end CLRS
Source