PricingWithTips 3DM dependency: Scratch_PricingWithTips_FixedShape3DM.Part3.Base.Valid.Literal
DefinitionPricingWithTips3DM_3a64b523d21161fe1251d130Part3BaseValidLiteralcomplexity-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_3a64b523d21161fe1251d130Part3BaseValidBound
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false
namespace PricingWithTips.FixedShape3DM
open Hardness Hardness.Cert Hardness.Sat3dm
theorem converted_clause_variable_coverage
(input : List CLRS.Chapter34.CNFSym)
{clause : CLRS.Chapter34.Clause}
(hclause : clause ∈ CLRS.Chapter34.decodeCNF input)
{l : Hardness.Literal ℕ}
(hl : l ∈ (clause.map CLRS3CNFBridge.certLiteral).map
Hardness.Cert.litOf) :
l.var ∈ variableList input := by
simp only [List.mem_map] at hl
obtain ⟨encoded, hencoded, rfl⟩ := hl
obtain ⟨literal, hliteral, rfl⟩ := hencoded
simpa [variableList] using
certified_literal_variable_lt input hclause hliteral
end PricingWithTips.FixedShape3DM
Source