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 shownnotto 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.