Computing the Stopping Distance of a Tanner Graph Is NP-Hard
Karunakaran Murali Krishnan, Priti Shankar · IEEE Transactions on Information Theory · 2007
Two decision problems related to the computation f stopping sets in Tanner graphs are shown to be NP-complete. It follows as a consequence that there exists no polynomial time algorithm for computing the stopping distance of a Tanner graph unless P = NP.