科研之友
微信
新浪微博
Facebook
分享链接
摘要
Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete by Vardy. The gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction in an earlier work. It was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2(log1-epsilon n) unless NP subset of RTIME(2(polylog(n))). In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless P = NP. We also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2(log1-epsilon n) unless NP subset of DTIME(2(polylog(n))). As the main technical contribution, for any constant 2/3 %26lt; rho %26lt; 1, we present a deterministic algorithm that given a positive integer s, runs in time poly(s) and constructs a code C of length poly(s) with an explicit Hamming ball of radius rho d(C), such that the projection at the first s coordinates sends the
- 出版日期2012-11
