On the Complexity of finding Stopping Distance in Tanner Graphs
arXiv:cs/0512101
Abstract
Two decision problems related to the computation of stopping sets in Tanner graphs are shown to be NP-complete. NP-hardness of the problem of computing the stopping distance of a Tanner graph follows as a consequence
A decision problem proved NP-complete in the earlier version was not equivalent to stopping distance problem for Tanner graphs. Now corrected