The complexity of computing the covering radius of a code
Aileen M. McLoughlin · IEEE Transactions on Information Theory · 1984
The problem of finding the covering radius of a binary linear code is shown to be nondeterministic polynomial (NP)-hard. In fact, a problem that is complete for the class\prod_{2}^{p}in the polynomial hierarchy is shown to be reducible to the covering-radius problem, so that finding the covering radius is strictly harder than any NP-complete problem unless the polynomial hierarchy collapses with NP =\prod_{2}^{p}.