On the Intractability of the Minimum Distance Problem for Regular LDPC Codes
2026-06-22 • Computational Complexity
Computational ComplexityInformation Theory
AI summaryⓘ
The authors study how hard it is to find the smallest number of errors a specific type of error-correcting code (called LDPC codes) can detect or fix. They show that even when these codes have regular patterns (fixed degrees for connections), determining this smallest number remains computationally very difficult (NP-complete and W[1]-complete). Their work uses special mathematical transformations to prove this difficulty while keeping the code structure intact. This clarifies the limits of exactly analyzing these codes under common design constraints.
Minimum Distance ProblemLDPC CodesTanner GraphsNP-completenessW[1]-completenessLeft Regular GraphsBiregular GraphsError-floorCodewordTrapping Sets
Authors
Chenyuan Jia, Qingqing Peng, Ke Liu, Guanghui Wang, Guiying Yan
Abstract
The minimum distance problem (MDP) for low-density parity-check (LDPC) codes is a central problem in coding theory and is closely related to the analysis of low-weight codewords and error-floor behavior. Although the unrestricted MDP is computationally intractable, its complexity under degree constraints that commonly occur in LDPC code design has remained less clear. In this paper, we study the MDP for left regular and biregular Tanner graphs. We prove that the problem is $\mathrm{NP}$-complete and $\mathrm{W}[1]$-complete for $J$-left regular Tanner graphs for every fixed $J\geq 3$, and also for $(3,3)$-regular bipartite graphs. We further establish $\mathrm{W}[1]$-completeness for $(J,K)$-regular instances for every fixed $J,K\geq 3$. The reductions are based on a degree-preserving transformation framework consisting of hyperedge decomposition, check node splitting, and controlled variable replication. These transformations transfer hardness between different degree distributions while preserving explicit bijections among nonzero codewords, even covers, and nonempty $(a,0)$-trapping sets. The results delineate the computational limits of exact LDPC code analysis under natural regularity constraints.