  Let $\RR$ be a real closed field (e.g. the field of real numbers) and
$\mathscr{S} \subset \RR^n$ be a semi-algebraic set defined as the set of
points in $\RR^n$ satisfying a system of $s$ equalities and inequalities of
multivariate polynomials in $n$ variables, of degree at most $D$, with
coefficients in an ordered ring $\ZZ$ contained in $\RR$. We consider the
problem of computing the {\em real dimension}, $d$, of $\mathscr{S}$. The real
dimension is the first topological invariant of interest; it measures the
number of degrees of freedom available to move in the set. Thus, computing the
real dimension is one of the most important and fundamental problems in
computational real algebraic geometry. The problem is ${\rm
NP}_{\mathbb{R}}$-complete in the Blum-Shub-Smale model of computation. The
current algorithms (probabilistic or deterministic) for computing the real
dimension have complexity $(s \, D)^{O(d(n-d))}$, that becomes $(s \,
D)^{O(n^2)}$ in the worst-case. The existence of a probabilistic or
deterministic algorithm for computing the real dimension with single
exponential complexity with a factor better than ${O(n^2)}$ in the exponent in
the worst-case, is a longstanding open problem. We provide a positive answer to
this problem by introducing a probabilistic algorithm for computing the real
dimension of a semi-algebraic set with complexity $(s\, D)^{O(n)}$.
