IEEE Transactions on Information Theory · 2007 · 58 citations · 14 references
Mathematical ProgrammingCircuit ComplexityComputational Complexity TheoryEngineeringTanner GraphComputational ComplexityStructural Graph TheoryP Versus Np ProblemDiscrete MathematicsCombinatorial OptimizationTanner GraphsLower BoundComputer ScienceAlgorithmic Information TheoryComputation FExponential AlgorithmGraph TheoryFormal MethodsTime ComplexityExtremal Graph Theory
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.
14
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.3K citations
Mathematical Programming, Computational Science, Engineering +6
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 16.9K citations
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.1K citations · Full text