Complexity of Decoding Positive-Rate Primitive Reed–Solomon Codes

It has been proved that the maximum likelihood decoding problem of Reed-Solomon codes is NP-hard. However, the length of the code in the proof is at most polylogarithmic in the size of the alphabet. For the complexity of maximum likelihood decoding of the primitive Reed-Solomon code, whose length is one less than the size of alphabet, the only known result states that it is at least as hard as the discrete logarithm in some cases where the information rate unfortunately goes to zero. In this paper, it is proved under a well known cryptography hardness assumption that: 1) There does not exist a randomized polynomial time maximum likelihood decoder for the Reed-Solomon code family [q, k(q)]_q, where k(x) is any function in Z⁺ → Z⁺ computable in time x^O(1) satisfying √x ≤ k(x) ≤ x - √x. 2) There does not exist a randomized polynomial time bounded-distance decoder for primitive Reed-Solomon codes at distance 2/3 + ϵ of the minimum distance for any constant 0 <; ϵ <; 1/3. In particular, this rules out the possibility of a polynomial time algorithm for maximum likelihood decoding problem of primitive Reed-Solomon codes of any rate under the assumption.