Complexity Classes for Cases Other Than "Worst Case"

Question

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.

Answer 1

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)

Answer 2

There are a number of classes that attempt to tackle various notions of average-case complexity. In the Complexity Zoo, some classes you might be interested in are:

AvgP

HeurP

DistNP

(NP,P-samplable)

Arora/Barak covers many, similar classes (in Ch 18), defining distP, distNP, and sampNP.

The exact relationship between all of these classes is characterized by Impagliazzo's Five Worlds, which was previously asked about in another question.

As far as the "best case" complexity question, I'm not sure I understand quite what you mean. Are you looking for EXP?

If you mean complexity classes defined in terms of the best case run time over all instances, this isn't a very good complexity measure a priori, since you'd only be looking at the trivial cases of any given problem.

Answer 3

[Expanding on Ryan Williams's answer and adding some search terms for you] Your notion of best case complexity already has a name: almost-everywhere (a.e.) hardness, or bi-immunity. (Ryan's example is of $TIME[T(n)]$-bi-immunity). If $\mathcal{C}$ is a complexity class, then a language $L$ is $\mathcal{C}$-immune if there is no infinite subset $L' \subseteq L$ such that $L' \in \mathcal{C}$. $L$ is $\mathcal{C}$-bi-immune if both $L$ and its complement $\overline{L} = \Sigma^* \backslash L$ are $\mathcal{C}$-immune. For example, it's not difficult to show that your definition of $\mathbf{BestE}$ is equivalent to the class of $E$-bi-immune sets.

(Historical aside: the notion of immunity was first developed by Post in 1944 in computability theory, long before P was even defined. Post actually considered "simple sets" -- a set is simple if its complement is immune. To a computability theorist, the word "immune" typically means "immune to computable sets." In that setting, immunity is equivalent to "immune to c.e. sets" since every infinite c.e. set contains an infinite computable one. I believe Post's paper was also the first to introduce the notion of many-one reduction, but I couldn't swear to that.)

Answer 4

Different cases make more sense when talking about algorithms, not problems. On the other hand, complexity classes are about problems , not algorithms. Therefore, the complexity class always being a worst-case for any algorithm is due to the definition.

In complexity, your goal is to know the number of resources needed to solve any instance of a given problem. Therefore, you know that for any given instance and algorithm, you are going to need those resources and nothing more.

In algorithm analysis, your goal is to ensure your algorithm has an upper bound for a resource, in any instance of the problem. A trivial bound is the complexity class of the problem, since no useful (one that does make uneccesary steps) algorithm takes more time than that. However, you can improve that bound given the specifics of the algorithm.

For example, let's say you are analyzing mergesort. Given the solution, you can confirm it in polynomial time, therefore SORTING is in NP. However, by analyzing, you can lower this down to $\Theta$(n*logn)

As for best case, it is trivial for every problem to find the least number of resources needed. Assume that the input is of length O(n) and the output of length O(m). Then the following TM M always runs in O(n)+O(m) for the best case :

M{Input,Instance,Solution}

1. Compare the given instance with the instance encoded in the machine.
2. If they are equal, return the solution encoded.
3. Else, do a brute-force search.

Answer 5

It seems that every problem has $O(1)$ best case complexity. Consider an algorithm that always outputs the solution to a particular instance. That instance is the best case.