Problems of Complexity in the Theory of Correcting Codes

An analysis is made of the complexity of solving such coding-theory problems as the creation of codes with good correcting properties and the encoding and decoding of such codes. The best available bounds on the complexity of solving these problems are given.