The intractability of computing the minimum distance of a code

被引：224
作者：
Vardy, A
机构：
[1] Coordinated Science Laboratory, University of Illinois, Urbana
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 1997年 / 43卷 / 06期
基金：
美国国家科学基金会;
关键词：
complexity; linear codes; minimum distance; NP-completeness;
D O I：
10.1109/18.641542
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
It is shown that the problem of computing the minimum distance of a binary linear code is NP-hard, and the corresponding decision problem is NP-complete. This result constitutes a proof of the conjecture of Berlekamp, McEliece, and van Tilborg, dating back to 1978. Extensions and applications of this result to other problems in coding theory are discussed.
引用
收藏
页码：1757 / 1766
页数：10
相关论文
共 40 条
[1]   CONSTRUCTION OF ASYMPTOTICALLY GOOD LOW-RATE ERROR-CORRECTING CODES THROUGH PSEUDORANDOM GRAPHS [J].
ALON, N ;
BRUCK, J ;
NAOR, J ;
NAOR, M ;
ROTH, RM .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1992, 38 (02) :509-516
[2]  
ALON N, 1996, COMMUNICATION OCT
[3]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[4]  
ARORA S, 1993, AN S FDN CO, P724
[5]  
Arora S., 1997, Approximation algorithms for NP-hard problems, P399
[6]  
ATJAI M, 1997, COMMUNICATION MAY
[7]  
ATJAI M, 1996, P 28 ANN ACM S THEOR, P99
[8]  
BARG A, 1994, PROBL PEREDACHI INF, V30, P23
[9]   INHERENT INTRACTABILITY OF CERTAIN CODING PROBLEMS [J].
BERLEKAMP, ER ;
MCELIECE, RJ ;
VANTILBORG, HCA .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1978, 24 (03) :384-386
[10]  
BERLEKAMP ER, 1968, ALGEBRAIC CODING THE
1234