This article is cited in 4 papers

Coding Theory

Some New NP-Complete Coding Problems

S. Barg


Abstract: We prove the NP-completeness of the basic decision problems for ternary linear codes. In particular, we prove that finding out whether a ternary linear code contains a vector of weight equal to the code length is NP-complete. In addition, we prove the hardness of minimum distance decoding for linear product codes with nontrivial factors.

UDC: 621.391.1:519.712

Received: 16.08.1993
Revised: 18.01.1994

 English version: Problems of Information Transmission, 1994, 30:3, 209–214

Bibliographic databases:

• 
•