A problem is said to be complete for a complexity class $\mathcal{C}$ if a) it is in $\mathcal{C}$ and b) every problem in $\mathcal{C}$ is log-space reducible to it. There are natural examples of NP-complete problems (SAT), P-complete problems (circuit-value), NL-complete problems (reachability), and so on.
Papadimitrou states that "semantic" complexity classes like (I think) BPP are less likely to admit complete problems. Then again, we do not actually know whether P = BPP or not, and if so, there would be BPP-complete problems. (There exist IP-complete problems, since IP=PSPACE, and determining whether a quantified boolean formula is satisfiable is PSPACE-complete.)
Question: Are there any natural complexity classes that can be shown not to have complete problems?
I think this question has to be modified slightly, because I would imagine $Time(n)$ has no complete problems because log-space reductions can introduce a polynomial factor.
So, in the word "natural," I include the assumption that the complexity class should be invariant under polynomial transformations (I don't know how to make this precise, but hopefully it is clear).
(Also, time or space bounds should be at least $\log n$, of course.)
Edit: A commenter has pointed me to an interesting result of Sipser that $\mathrm{BPP}^M$ for $M$ a suitable oracle does not have complete problems. Is the same true for a (less fancy) class of the form $\bigcup_f TIME(f)$, where the union is over a class of recursive functions $f$ that are all polynomially related to each other? (Same for $\bigcup_f NTIME(f)$, and ditto for space.
Best Answer
The zoo of complexity classes extends naturally into the realm of computability theory and beyond, to descriptive set theory, and in these higher realms there are numerous natural classes which have no members that are complete, even with respect to far more generous notions of reduction than the one you mention.
For example, consider the class Dec of all decidable sets of natural numbers. There can be no decidable set $U$ such that every other decidable set $A$ reduces to it in time uniformly bounded by any computable function $f$ (even iterated exponentials, or the Ackerman function, etc.). In particular, it has no member that is complete in your sense. If there were such a member, then we would be able to consruct a computable enumeration $A_0$, $A_1$, $\ldots$ containing all decidable sets, which is impossible since then we could diagonalize against it: the set of $n$ such that $n\notin A_n$ would be computable, but it can't be on the list.
The class of all arithmetically definable sets is obtained by closing the decidable sets (or much less) under projection from $\mathbb{N}^{n+1}\to \mathbb{N}^n$ and under Boolean combinations. The members of this class are exactly the sets that are defined by a first order formula over the structure $\langle\mathbb{N},+,\cdot,\lt\rangle$, and the hierarchy is stratified by the complexity of these definitions. This class has no member that is complete with respect to any computable reduction, and even with respect to any arithmetically definable reduction of bounded complexity, for in this case the hierarchy would collapse to some level $\Sigma_n$, which is known not to occur.
A similar argument works for the hyperarithmetic hiearchy, which can have no universal member hyperarithmetic reductions of any fixed complexity.
And similarly for the projective hiearchy on sets of reals.
The general phenomenon is that there are numerous hierarchies growing from computability theory into descriptive set theory which are all known to exhibit strictly proper growth in such a way that prevents them from having universal members.