More specifically, suppose I have a rational curve on a complete intersection, and I know that the relative Hilbert Scheme is not smooth at the point corresponding to my rational curve. Is there any algorithm that will eventually tell me whether the Hilbert Scheme is reduced or not there?
Just to make it harder, this curve happens to pass through the singular locus of the complete intersection.
Showing nonreducedness of a Hilbert scheme is a hard question in general. The most direct algorithm would involve producing a Grobner basis for the defining ideal of the component in question, and then computing its radical and seeing if the two are equal. But with the exception of rather simple cases, this computation is not going to be feasible. Here are two shortcut answers that I've seen in the past.
You could show that the entire component of the Hilbert scheme in question is nonreduced. Mumford produces a famous such example, in his "Further Pathologies" paper from 1962. I have also seen works by J.O. Kleppe and some by Scott Nollet which provide many further examples and techniques.
You could produce a global description of component of the Hilbert scheme in question. For instance, perhaps the component is parametrized by something that you understand (a Grassmanian, say). The best example of this that I've ever read is Vainsencher-Avritzer "Compactifying the space of ellpitic quartic curves".
