It seems to me that you're basically asking for an algorithm. The one I previously proposed fails (as noted by Mariano), so let me try something else.
Disclaimer. I am not an expert at all. I hope I haven't made any more mistakes.
Reference. A great reference is Eisenbud's Commutative Algebra with a view towards Algebraic Geometry.
Answer to your question. The first thing you need to do, of course, is compute a minimal set of generators for your ideal $I$. We can actually do more: compute a minimal free resolution (see Eisenbud, Lemma 19.4 for definition and existence)
$$0 \to P_r \to \ldots, \to P_0 \to I \to 0$$
of the finitely generated module $I$ over the (graded!) ring $k[x_0,\ldots,x_n]$. It is a theorem that any other resolution will contain this minimal resolution as a summand (see Eisenbud, Theorem 20.2 for the local case, and note that it also works in the graded case, cf. Exercise 20.1). This justifies the name 'minimal resolution'.
In particular, the rank of $P_0$ is the number of generators required, and this also equals the dimension of $I/(x_0,\ldots,x_n)I$ as $k$-vector space (Lemma 19.4).
Once you have a minimal set of generators $g_1,\ldots,g_r$ for $I$, it is relatively straightforward: now we just have to check that $V(I) \subseteq \mathbb P^n$ has dimension $n-r$. For simplicity, let's assume $r \leq n$, so that $V(I) \neq \varnothing$. You would have to think about how you can check something is a complete intersection when there are more than $n$ generators. (For example, $(x_0,\ldots,x_n)^2$ cannot be generated by fewer than $\frac{(n+1)(n+2)}{2}$ elements, yet its vanishing set is empty, which is (?) a complete intersection.)
There are many ways of proceeding. Let me list a few:
- One can try to compute the transcendence degree of the field $K = \operatorname{Frac} k[x_0,\ldots,x_n]/I$. In characteristic $0$, it is necessary and sufficient that $\Omega_{K/k}^1$ has dimension $n+1-r$, i.e. that the Jacobian of $g_1,\ldots,g_r$ has maximal rank (i.e. $r$) at the generic point of $k[x_0,\ldots,x_n]/I$.
- One can probably compute the transcendence degree through elimination theory as well (again, not an expert). Eisenbud might tell you a bit about what I mean by elimination theory.
- The first two approaches only work when $I$ is a prime ideal. In general, one can compute the Hilbert polynomial of the graded ring $k[x_0,\ldots,x_n]/I$. It should be a polynomial of degree $n-r$ for $V(I)$ to be a complete intersection. See Theorem 15.26 in Eisenbud for a way to compute the Hilbert polynomial.
- Etc.
So the best case is if $f_1,\ldots,f_s$ are a minimal set of generators of a prime ideal $I$ over a field of characteristic $0$. In that case, you only have to check that the Jacobian is generically (on $V(I)$) of rank $s$. Again, there are multiple ways you can do this:
- You can check that none of the $s\times s$-minors is in $I$. See Eisenbud, section 15.10.1 for computability of ideal membership.
- You can check that not all of the vanishing loci of the $s\times s$-minors contain $I$, for instance by some geometric argument (this is not an algorithm, but maybe how you would do it in practice).
Example. The easiest example I know of something that is not a complete intersection is the twisted cubic in $\mathbb P^3$. If the embedding is
\begin{align*}
\mathbb P^1 &\mapsto \mathbb P^3\\
[u,v] &\mapsto [u^3, u^2v, uv^2, v^3],
\end{align*}
then it is cut out by $xz-y^2$, $yw-z^2$, and $xw-yz$. This is a minimal set of generators, for one can check that $I/(x,y,z,w)I$ is $3$-dimensional.
The Jacobian is
$$\left(\begin{array}{ccc}z & -2y & x & 0 \\ 0 & w & -2z & y \\ w & -z & -y & x\end{array}\right).$$
The $3\times 3$-minors are
\begin{align}
3zwy-w^2x-2z^3,\\ zwx-2y^2w+z^2y,\\ -2z^2x+xyw+y^2z,\\ 3xyz-2y^3-wx^2,
\end{align}
all of which are easily seen to be in $I$. We conclude that $V(I)$ is not a complete intersection.
Of course, if we already knew that these three relations are minimal relations cutting out a $\mathbb P^1$, then it is clear that it is not a complete intersection, by an easy dimension count. But in general, you do not know a priori what the isomorphism type of the subvariety is.
