Proceedings of Workshop on Coding and Cryptography '99, pp. 21-27, January 1999.
Iiro HONKALA
Department of Mathematics
University of Turku
20014 Turku, Finland
e-mail: honkala@utu.fi
&
Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
e-mail: lobstein@infres.enst.fr
Abstract. The problem of upper bounding the minimum norm of a binary code is shown to be co-NP-complete, and $Pi_2$-complete if the code is known to be linear and the input consists of a parity check matrix for the code.