Do we have complexity classes with respect to, say, average-case complexity? For instance, is there a (named) complexity class for problems which take expected polynomial time to decide?
Another question considers the best case complexity, exemplified below:
Is there a class of (natural) problems whose decision requires at least exponential time?
To clarify, consider some EXP-complete language $L$. Obviously, not all instances of $L$ require exponential time: There are instances which can be decided even in polynomial time. So, the best case complexity of $L$ is not exponential time.
EDIT: Since several ambiguities arose, I want to try to clarify it even more. By "best case" complexity, I mean a complexity class whose problems' complexity is lower bounded by some function. For instance, define BestE as the class of languages which cannot be decided in time less than a some linear exponential. Symbolically, let $M$ denote an arbitrary Turing machine, and $c$, $n_0$, and $n$ be natural numbers:
$L \in \mathbf{BestE} \Leftrightarrow$ $\quad (\exists c)(\forall M)[(L(M) = L) \Rightarrow (\exists {n_0})(\forall n > {n_0})(\forall x \in {\{0,1\}^n})[T(M(x)) \ge {2^{c|x|}}]]$
where $T(M(x))$ denotes the times it takes before $M$ halts on input $x$.
I accept that defining such class of problems is very odd, since we are requiring that, every Turing machine $M$, regardless of its power, cannot decide the language in time less than some linear exponential.
Yet notice that the polynomial-time counterpart (BestP) is natural, since every Turing machine requires time $|x|$ to at least read its input.
PS: Maybe, instead of quantifying as "for all Turing machine $M$," we have to limit it to some pre-specified class of Turing machines, such as polynomial-time Turing machines. That way, we can define classes like $\mathbf{Best(n^2)}$, which is the class of languages requiring at least quadratic time to be decided on polynomial-time Turing machines.
PS2: One can also consider the circuit-complexity counterpart, in which we consider the least circuit size/depth to decide a language.