  In this paper, we consider the problem of deciding the existence of real
solutions to a system of polynomial equations having real coefficients, and
which are invariant under the action of the symmetric group. We construct and
analyze a Monte Carlo probabilistic algorithm which solves this problem, under
some regularity assumptions on the input, by taking advantage of the symmetry
invariance property. The complexity of our algorithm is polynomial in $d^s,
{{n+d} \choose d}$, and ${{n} \choose {s+1}}$, where $n$ is the number of
variables and $d$ is the maximal degree of $s$ input polynomials defining the
real algebraic set under study. In particular, this complexity is polynomial in
$n$ when $d$ and $s$ are fixed and is equal to $n^{O(1)}2^n$ when $d=n$.
