On the inherent intractability of certain coding problems (Corresp.) 论文
1978IEEE Transactions on Information Theory引用 1495
Coding theory and cryptographygraph theory and CDMA systemsError Correcting Code Techniques
详细信息
- 发表期刊/会议
- IEEE Transactions on Information Theory
- 发表日期
- 1978-05-01
- 发表年份
- 1978
关键词
Coding theory and cryptographygraph theory and CDMA systemsError Correcting Code Techniques
摘要
MEMBER, IEEE, AND HENK C. A. V~ TILBORG The fact that the general decoding problem for linear codes and the general problem of finding the weights of a linear code are both NP-complete is shown. This strongly suggests, but does not rigorously imply, that no algorithm for either of these problems which runs in polynomial time exists.