Section III, pp. 385–386 — the code with parity-check matrix A has a word of weight 3n² + 4n iff the triples admit a matching
ProvedIntractableCoding.Weights.subspace_reduction_ifflinear-codesnp-completenessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1three-dimensional-matching
Let with and , and let be the matrix built from the triple incidence matrix (top rows followed by copies of ; lower rows the identity ). Then
that is, the SUBSPACE WEIGHTS instance is a yes-instance exactly when admits a matching.
Together with the polynomial-time computability of this is the reduction of THREE-DIMENSIONAL MATCHING to SUBSPACE WEIGHTS.
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 code with parity-check matrix `A = subspaceMatrix I` has a word of weight
`3n² + 4n` iff the set of triples admits a matching. -/
theorem subspace_reduction_iff (I : ThreeDMInstance) :
ThreeDMYes I ↔ SubspaceWeightsYes (subspaceOf3DM 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, pp. 385–386, Section III, reduction of THREE-DIMENSIONAL MATCHING to SUBSPACE WEIGHTS
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.