Complexity Classes for Cases Other Than "Worst Case" 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.
Although I can't quite parse your definitions, you should know that much stronger time hierarchies are known, in particular "almost everywhere" time hierarchies. 

Here is the formal statement: for every time bound $T(n)$, there is a language $L \in TIME[T(n)]$ with the property that every deterministic algorithm that correctly recognizes $L$ must run in time asymptotically greater than $t(n)$ on all but finitely many inputs, for sufficiently small time $t(n)$.   

"Sufficiently small" means $t(n) \log t(n) \leq o(T(n))$.

Suppose we choose $T(n)=2^n$ for an example, and obtain a hard language $L$. Then, any algorithm that correctly recognizes $L$ must take at least $2^n/n^2$ time on all inputs past a certain length. This seems to be what you're looking for in your class BestE.

Reference:


  John G. Geske, Dung T. Huynh, Joel I. Seiferas: A Note on Almost-Everywhere-Complex Sets and Separating Deterministic-Time-Complexity Classes Inf. Comput. 92(1): 97-104 (1991)