RAIRO Informatique Théorique et Applications, Vol. 21, No. 1, pp. 25-32, 1987.
Antoine LOBSTEIN & Gérard COHEN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
Abstract. In a paper published in 1978, Berlekamp et al. conjecture the nonexistence of a polynomial algorithm for computing the minimum weight of a linear code (if P is not equal to NP). We here provide further evidence to support this conjecture, by proving NP-completeness of a few related problems, including:
- Problem $\Pi_7$: the minimal weight codeword searched for must begin with a 1.
- Problem $\Pi_8$: the minimal weight codeword searched for must have a fraction p/(p+1) of all its 1 on its first components.