  For generalized Reed-Solomon codes, it has been proved \cite{GuruswamiVa05}
that the problem of determining if a received word is a deep hole is
co-NP-complete. The reduction relies on the fact that the evaluation set of the
code can be exponential in the length of the code -- a property that practical
codes do not usually possess. In this paper, we first presented a much simpler
proof of the same result. We then consider the problem for standard
Reed-Solomon codes, i.e. the evaluation set consists of all the nonzero
elements in the field. We reduce the problem of identifying deep holes to
deciding whether an absolutely irreducible hypersurface over a finite field
contains a rational point whose coordinates are pairwise distinct and nonzero.
By applying Schmidt and Cafure-Matera estimation of rational points on
algebraic varieties, we prove that the received vector $(f(\alpha))_{\alpha \in
\F_q}$ for Reed-Solomon $[q,k]_q$, $k < q^{1/7 - \epsilon}$, cannot be a deep
hole, whenever $f(x)$ is a polynomial of degree $k+d$ for $1\leq d < q^{3/13
-\epsilon}$.
