Section III, p. 385 — the COSET WEIGHTS instance (B, 11⋯1, |T|) is a yes-instance iff the triples admit a matching
ProvedIntractableCoding.Weights.coset_reduction_iffdecodingnp-completenessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1three-dimensional-matching
Let with , and let be its triple incidence matrix. Then admits a matching if and only if the COSET WEIGHTS instance is a yes-instance:
Together with the polynomial-time computability of the map this is the reduction of THREE-DIMENSIONAL MATCHING to COSET WEIGHTS. Note that COSET WEIGHTS asks for weight at most while a matching uses exactly rows.
Differences from the source:
- encoding: input a set U ⊆ T × T × T of triples over a finite set T → ThreeDMInstance = ⟨n, edge⟩ with T = Fin n and U = {(a,b,c) | edge a b c}; the triples listed lexicographically, the incidence columns in three blocks a, n + b, 2n + c; reason: any finite T is in bijection with Fin |T|; the row and column orders change no weight and no instance's answer
- encoding: binary matrix A, row vector x, xA computed mod 2 → Matrix (Fin m) (Fin n) (ZMod 2), Matrix.vecMul x A, Hamming weight hammingNorm; reason: GF(2) = ZMod 2; xA with x indexed by the rows is Matrix.vecMul
Preamble
import Mathlib import Definitions.Def_IntractableCoding_Weights_Reductions
Formal statement
namespace IntractableCoding.Weights
open PricingWithTips
/-- The COSET WEIGHTS instance `(B, 11⋯1, |T|)` built from a 3DM instance is a yes-instance
iff the 3DM instance has a matching. -/
theorem coset_reduction_iff (I : ThreeDMInstance) :
ThreeDMYes I ↔ CosetWeightsYes (cosetOf3DM I) := by sorry
end IntractableCoding.Weights
Source
Berlekamp, McEliece & van Tilborg, On the Inherent Intractability of Certain Coding Problems, IEEE Trans. Inform. Theory IT-24(3), 1978, https://doi.org/10.1109/TIT.1978.1055873, p. 385, Section III, reduction of THREE-DIMENSIONAL MATCHING to COSET WEIGHTS
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.