  We investigate the complexity of the separation problem associated to classes
of regular languages. For a class C, C-separation takes two regular languages
as input and asks whether there exists a third language in C which includes the
first and is disjoint from the second. First, in contrast with the situation
for the classical membership problem, we prove that for most classes C, the
complexity of C-separation does not depend on how the input languages are
represented: it is the same for nondeterministic finite automata and monoid
morphisms. Then, we investigate specific classes belonging to finitely based
concatenation hierarchies. It was recently proved that the problem is always
decidable for levels 1/2 and 1 of any such hierarchy (with inefficient
algorithms). Here, we build on these results to show that when the alphabet is
fixed, there are polynomial time algorithms for both levels. Finally, we
investigate levels 3/2 and 2 of the famous Straubing-Th\'erien hierarchy. We
show that separation is PSPACE-complete for level 3/2 and between PSPACE-hard
and EXPTIME for level 2.
