pith. sign in

arxiv: 2606.23161 · v1 · pith:MRGX4KRUnew · submitted 2026-06-22 · 💻 cs.CC · cs.IT· math.IT

On the Intractability of the Minimum Distance Problem for Regular LDPC Codes

Chenyuan Jia , Qingqing Peng , Ke Liu , Guanghui Wang , Guiying Yan This is my paper

Pith reviewed 2026-06-26 06:18 UTC · model grok-4.3

classification 💻 cs.CC cs.ITmath.IT
keywords minimum distance problemLDPC codesNP-completenessW[1]-completenessTanner graphsregular bipartite graphstrapping sets
0
0 comments X

The pith

The minimum distance problem is NP-complete for J-left regular Tanner graphs with any fixed J at least 3.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that computing the minimum distance remains NP-complete and W[1]-complete when the Tanner graph is restricted to J-left regular form for every fixed J of 3 or higher, and likewise for (3,3)-regular bipartite graphs. It further shows W[1]-completeness for all fixed (J,K)-regular instances with J and K at least 3. The argument proceeds by reductions that employ hyperedge decomposition, check-node splitting, and controlled variable replication to move hardness across degree distributions while keeping explicit one-to-one correspondences among nonzero codewords, even covers, and nonempty (a,0)-trapping sets. A reader would care because these are exactly the regularity constraints used in most practical LDPC constructions, so the result limits what can be computed exactly about low-weight codewords and error floors.

Core claim

We prove that the minimum distance problem is NP-complete and W[1]-complete for J-left regular Tanner graphs for every fixed J≥3, and also for (3,3)-regular bipartite graphs. We further establish W[1]-completeness for (J,K)-regular instances for every fixed J,K≥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.

What carries the argument

The degree-preserving transformation framework of hyperedge decomposition, check node splitting, and controlled variable replication, which transfers hardness across regular degree sequences while maintaining bijections on nonzero codewords, even covers, and (a,0)-trapping sets.

If this is right

  • Exact minimum-distance computation is intractable for all J-left regular Tanner graphs with fixed J≥3 unless P=NP.
  • The same intractability holds for every fixed (J,K)-regular bipartite graph with J,K≥3.
  • Related tasks of enumerating even covers and nonempty (a,0)-trapping sets inherit the same hardness under these regularity constraints.
  • Error-floor analysis that relies on exact minimum distance is computationally limited for the regular LDPC codes used in practice.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction technique might be usable to prove hardness for other coding-theoretic quantities such as stopping-set size under fixed-degree constraints.
  • Practical code design for regular LDPC codes will likely continue to depend on upper bounds or Monte-Carlo simulation rather than exact minimum-distance computation.
  • The framework could be tested on small explicit regular graphs to verify whether the preserved bijections hold numerically for distances up to a chosen bound.

Load-bearing premise

The transformations produce graphs whose minimum distances match exactly via the preserved bijections on codewords and covers.

What would settle it

A polynomial-time algorithm that correctly outputs the minimum distance for every 3-left regular Tanner graph would falsify the NP-completeness result.

Figures

Figures reproduced from arXiv: 2606.23161 by Chenyuan Jia, Guanghui Wang, Guiying Yan, Ke Liu, Qingqing Peng.

Figure 1
Figure 1. Figure 1: Reduction flow for the MDP under left regular and biregular degree [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: illustrates the definition of an even cover. The red hyperedges are the selected hyperedges in Y, while the black hyperedge belongs to the hypergraph but is not selected. In the selected sub-hypergraph, every vertex is incident with exactly two red hyperedges, and hence every vertex has even degree with respect to Y. Therefore, the red hyperedges form an even cover. e1 e2 e3 e4 v1 v2 v3 v4 v5 v6 Y = {e1, e… view at source ↗
Figure 3
Figure 3. Figure 3: Hypergraph representation of a Tanner graph variable node and its [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Example of decomposing a hyperedge of size six. Numbers denote [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Matrix representation of a bipartite graph after the check node splitting operation. Shaded entries indicate nonzero positions; all remaining entries are [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Example of expanding a variable node ξ with replication factor m = 4. Numbers denote replicated variables, and letters denote auxiliary check nodes. The algorithm can be implemented efficiently with a single pass through the replication chain. It introduces m replication nodes and a corresponding number of auxiliary check nodes and edges through a loop that iterates m/2 times, with each iteration performin… view at source ↗
Figure 7
Figure 7. Figure 7: Second phase of the reduction in the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p014_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Schematic reduction from the (3, 3)-regular case to the (4, 3)-regular case using copies and global check nodes. one would need a linearity-preserving version of the reduction underlying Theorem 20; the main challenge is to transform a general J-uniform, K-regular hypergraph into a linear one while preserving even covers and their minimum cardinalities. The mapping perspective developed earlier suggests th… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript proves NP-completeness and W[1]-completeness of the minimum distance problem for J-left regular Tanner graphs (every fixed J≥3) and for (3,3)-regular bipartite graphs, plus W[1]-completeness for (J,K)-regular instances (every fixed J,K≥3). The proofs rest on a degree-preserving transformation framework (hyperedge decomposition, check node splitting, controlled variable replication) that is asserted to transfer hardness while preserving explicit bijections among nonzero codewords, even covers, and nonempty (a,0)-trapping sets.

Significance. If the reductions are correct, the results would establish that exact minimum-distance computation remains intractable even under the fixed-degree constraints that arise in standard LDPC constructions, thereby clarifying the computational limits of exact code analysis and error-floor studies.

major comments (1)
  1. [Abstract] Abstract: the central claim that the reductions preserve explicit bijections among nonzero codewords (and the related objects) is stated without any proof details, verification steps, or edge-case handling; because the completeness statements rest entirely on these bijections, the absence of the supporting arguments is load-bearing.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed review. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the reductions preserve explicit bijections among nonzero codewords (and the related objects) is stated without any proof details, verification steps, or edge-case handling; because the completeness statements rest entirely on these bijections, the absence of the supporting arguments is load-bearing.

    Authors: The abstract provides a high-level summary of the results. The explicit constructions and verifications of the bijections (including weight preservation, even covers, and (a,0)-trapping sets) are given in full in Sections 3 and 4. Section 3 details the hyperedge decomposition and check-node splitting for J-left regular instances with direct mappings and edge-case checks for J=3. Section 4 handles the (J,K)-regular case via controlled replication, again with explicit bijections and verification steps. These sections contain the required arguments. No change to the abstract is needed, as abstracts are not expected to contain full proofs. revision: no

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes NP- and W[1]-completeness of the minimum distance problem for regular LDPC codes via explicit degree-preserving reductions (hyperedge decomposition, check node splitting, controlled variable replication) that maintain weight-preserving bijections between codewords and related objects. These are standard Karp-style reductions from known hard problems rather than any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. The derivation chain is self-contained against external benchmarks in complexity theory; no equation or step reduces the target result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the correctness of the three named graph transformations and on the standard definitions of NP-completeness and W[1]-completeness; no numerical parameters are fitted and no new entities are postulated.

axioms (1)
  • standard math Standard definitions and closure properties of NP-completeness and W[1]-completeness under polynomial-time reductions
    Invoked throughout the reduction framework described in the abstract.

pith-pipeline@v0.9.1-grok · 5755 in / 1249 out tokens · 34343 ms · 2026-06-26T06:18:20.252128+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references

  1. [1]

    Low-density parity-check codes,

    R. Gallager, “Low-density parity-check codes,”IRE Transactions on Information Theory, vol. 8, no. 1, pp. 21–28, 1962

    1962

  2. [2]

    Error floors of ldpc codes,

    T. Richardson, “Error floors of ldpc codes,” inProceedings of the An- nual Allerton Conference on Communication, Control, and Computing, vol. 41, no. 3, 2003, pp. 1426–1435

    2003

  3. [3]

    The parametrized complexity of some fundamental problems in coding theory,

    R. G. Downey, M. R. Fellows, A. Vardy, and G. Whittle, “The parametrized complexity of some fundamental problems in coding theory,”SIAM Journal on Computing, vol. 29, no. 2, pp. 545–570, 1999

    1999

  4. [4]

    The hardness of approximate optima in lattices, codes, and systems of linear equations

    S. Arora, L. Babai, J. Stern, and Z. Sweedyk, “The hardness of approximate optima in lattices, codes, and systems of linear equations.” J. Comput. Syst. Sci., vol. 54, no. 2, pp. 317–331, 1997. 18

    1997

  5. [5]

    The intractability of computing the minimum distance of a code,

    A. Vardy, “The intractability of computing the minimum distance of a code,”IEEE Transactions on Information Theory, vol. 43, no. 6, pp. 1757–1766, 1997

    1997

  6. [6]

    Feige,Small Linear Dependencies for Binary Vectors of Low Weight

    U. Feige,Small Linear Dependencies for Binary Vectors of Low Weight. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 283–307

    2008

  7. [7]

    A simple and sharper proof of the hypergraph moore bound,

    J.-T. Hsieh, P. K. Kothari, and S. Mohanty, “A simple and sharper proof of the hypergraph moore bound,” inProc. of the 2023 Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA). Philadelphia, PA, USA: SIAM, 2023, pp. 2324–2344

    2023

  8. [8]

    On the inherent intractability of certain coding problems (corresp.),

    E. Berlekamp, R. McEliece, and H. van Tilborg, “On the inherent intractability of certain coding problems (corresp.),”IEEE Transactions on Information Theory, vol. 24, no. 3, pp. 384–386, 1978

    1978

  9. [9]

    Hardness of approximating the minimum distance of a linear code,

    I. Dumer, D. Micciancio, and M. Sudan, “Hardness of approximating the minimum distance of a linear code,”IEEE Transactions on Information Theory, vol. 49, no. 1, pp. 22–37, 2003

    2003

  10. [10]

    Hardness results on finding leafless elementary trapping sets and elementary absorbing sets of ldpc codes,

    A. Dehghan and A. H. Banihashemi, “Hardness results on finding leafless elementary trapping sets and elementary absorbing sets of ldpc codes,”IEEE Transactions on Information Theory, vol. 65, no. 7, pp. 4307–4315, 2019

    2019

  11. [11]

    On finding bipartite graphs with a small number of short cycles and large girth,

    ——, “On finding bipartite graphs with a small number of short cycles and large girth,”IEEE Transactions on Information Theory, vol. 66, no. 10, pp. 6024–6036, 2020

    2020

  12. [12]

    Parameterized intractability of even set and shortest vector problem,

    A. Bhattacharyya, E. Bonnet, L. Egri, S. Ghoshal, K. C. S., B. Lin, P. Manurangsi, and D. Marx, “Parameterized intractability of even set and shortest vector problem,”J. ACM, vol. 68, no. 3, Mar. 2021

    2021

  13. [13]

    Small even covers, locally decodable codes and restricted subgraphs of edge-colored kikuchi graphs,

    J.-T. Hsieh, P. K. Kothari, S. Mohanty, D. M. Correia, and B. Sudakov, “Small even covers, locally decodable codes and restricted subgraphs of edge-colored kikuchi graphs,”International Mathematics Research Notices, vol. 2025, no. 5, p. rnaf045, 03 2025

    2025

  14. [14]

    M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences), first edition ed. W. H. Freeman, 1979

    1979

  15. [15]

    M. G. J ¨org Flum,Parameterized complexity, first edition ed. Springer Berlin, Heidelberg, 2006

    2006

  16. [16]

    R. G. Downey and M. R. Fellows,Fundamentals of parameterized complexity, first edition ed. Springer London, 2013

    2013

  17. [17]

    E. D. Demaine, W. Gasarch, and M. Hajiaghayi,Computational In- tractability: A Guide to Algorithmic Lower Bounds. MIT Press, 2026

    2026

  18. [18]

    Regul ¨are graphen gegebener taillenweite mit minimaler knotenzahl (in german),

    P. Erd ¨os and H. Sachs, “Regul ¨are graphen gegebener taillenweite mit minimaler knotenzahl (in german),”Wiss. Z. Martin-Luther-Univ. Halle- Wittenberg Math.-Natur. Reihe, vol. 12, pp. 251–257, 1963

    1963

  19. [19]

    On the existence of regular n-graphs with given girth,

    N. Sauer, “On the existence of regular n-graphs with given girth,” Journal of Combinatorial Theory, Series A, vol. 9, pp. 144–147, 1970

    1970

  20. [20]

    Globally coupled ldpc codes,

    J. Li, S. Lin, K. Abdel-Ghaffar, W. E. Ryan, and D. J. Costello, “Globally coupled ldpc codes,” in2016 Information Theory and Applications Workshop (ITA), 2016, pp. 1–10. Chenyuan Jiareceived the B.Sc. degree in mathematics from Ocean Uni- versity of China, in 2024. He is currently pursuing the Ph.D. degree in mathematics with the School of Mathematics, S...

    2016

  21. [21]

    Guanghui Wangreceived the B.S

    His research interests include coding theory and graph theory and its applications. Guanghui Wangreceived the B.S. degree in mathematics from Shandong University, China, and the Ph.D. degree from the Universit´e Paris-Sud, France, in 2001 and 2007, respectively. He is currently a Professor with the School of Mathematics, Shandong University, Shandong, Chi...

    2001