  The complexity of maximal likelihood decoding of the Reed-Solomon codes
$[q-1, k]_q$ is a well known open problem. The only known result in this
direction 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, we
remove the rate restriction and prove that the same complexity result holds for
any positive information rate. In particular, this resolves an open problem
left in [4], and rules out the possibility of a polynomial time algorithm for
maximal likelihood decoding problem of Reed-Solomon codes of any rate under a
well known cryptographical hardness assumption. As a side result, we give an
explicit construction of Hamming balls of radius bounded away from the minimum
distance, which contain exponentially many codewords for Reed-Solomon code of
any positive rate less than one. The previous constructions only apply to
Reed-Solomon codes of diminishing rates. We also give an explicit construction
of Hamming balls of relative radius less than 1 which contain subexponentially
many codewords for Reed-Solomon code of rate approaching one.
