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

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 =

.