On the subset sum problem over finite fields (Q958604)

The authors study the subset sum problem over finite fields which is known to be NP-complete. They study the number of solutions of the problem and in some cases obtain explicit or asymptotic formulas for the number of solutions. This problem has a natural application in the decoding of generalized Reed-Solomon codes using maximum likelihood decoding. Bounds are given in this case and deep holes are defined to be where the upper bound is met. The results of the paper are used to give some information as to when a vector is a deep hole.