On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
arXiv:0704.2258
Abstract
We prove that approximating the size of stopping and trapping sets in Tanner graphs of linear block codes, and more restrictively, the class of low-density parity-check (LDPC) codes, is NP-hard. The ramifications of our findings are that methods used for estimating the height of the error-floor of moderate- and long-length LDPC codes based on stopping and trapping set enumeration cannot provide accurate worst-case performance predictions.
16 pages, 6 figure, submitted journal version