By concatenating linear-time codes with small, good codes, it is possible to construct in polynomial time a family of asymptotically good codes that approach the Shannon bound that can be encoded and decoded in linear time. Moreover, their probability of decoder error is exponentially small in the block length of the codes. In this survey, we will explain exactly what this statement means, how it is derived, and what problems in the complexity of error-correcting codes remain open. Along the way, we will survey some key developments in the complexity of error-correcting codes.