<p>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:</p>

<p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:A#avgp" rel="nofollow noreferrer">AvgP</a></p>

<p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:H#heurp" rel="nofollow noreferrer">HeurP</a></p>

<p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#distnp" rel="nofollow noreferrer">DistNP</a></p>

<p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nppsamp" rel="nofollow noreferrer">(NP,P-samplable)</a></p>

<p><a href="http://www.cs.princeton.edu/theory/complexity/" rel="nofollow noreferrer">Arora/Barak</a> covers many, similar classes (in Ch 18), defining distP, distNP, and sampNP.</p>

<p>The exact relationship between all of these classes is characterized by Impagliazzo's Five Worlds, which was previously asked about <a href="https://cstheory.stackexchange.com/questions/1026/status-of-impagliazzos-worlds">in another question</a>.</p>

<p>As far as the "best case" complexity question, I'm not sure I understand quite what you mean. Are you looking for <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#exp" rel="nofollow noreferrer">EXP</a>?</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-20T15:33:01.320Z
Very well done! That's what I needed for the average-case complexity part of the question. Regarding the "best-case" part, I noticed that the original statement of the question was vague. My bad! I have edited it a lot, so please consider reading it again.
Sadeq Dousti
CC BY-SA 3.0
2010-09-20T13:38:53.490Z
2015-11-02T01:10:02.910Z
2017-04-13T12:32:28.117Z
Daniel Apon
<p>[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.</p>

<p>(Historical aside: the notion of immunity was first developed by <a href="https://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read/1517#1517">Post in 1944</a> 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.)</p>

CC BY-SA 2.5
2010-09-20T17:19:26.460Z
Actually, his definition only has $M$ accepting inputs in $L$, not rejecting inputs not in $L$... provided you put the condition $M(x)=1$ in the right place.
Ryan Williams
CC BY-SA 2.5
2010-09-20T17:29:06.367Z
Thanks a lot Joshua. Your answer complements that of Ryan's. Just one edit: In the definition of C-immunity, one "prime" is missing (it should read: no infinite subset $L'$ such that $L' \in C$.)
Sadeq Dousti
CC BY-SA 2.5
2010-09-20T18:45:56.123Z
@Sadeq: fixed, thanks.  @Ryan: True (or it was a couple hours ago: he has since updated the definition). Then it would be immunity instead of bi-immunity.  Either way, mainly I just wanted to point out the keyword "immunity."
Joshua Grochow
CC BY-SA 2.5
2010-09-20T17:11:44.300Z
2010-09-20T19:05:27.763Z
2017-04-13T12:32:28.743Z
Joshua Grochow
<p>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. </p>

<p>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. </p>

<p>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. </p>

<p>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)</p>

<p>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 :</p>

<p>M{Input,Instance,Solution}</p>

<ol>
<li>Compare the given instance with the instance encoded in the machine.</li>
<li>If they are equal,  return the solution encoded.</li>
<li>Else, do a brute-force search.</li>
</ol>

CC BY-SA 2.5
2010-09-20T13:56:35.863Z
2010-09-20T13:56:35.863Z
chazisop
<p>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.</p>

CC BY-SA 2.5
2010-09-20T14:51:14.570Z
I do not think that that counts as a correct algorithm for the problem.  However, your algorithm can be modified so that it first checks whether the input is equal to the particular instance which you have predetermined (in O(1) time).  If it is, it outputs the precomputed answer.  If not, you solve the given instance by any means.  Thinking about it, _any_ correct algorithm runs in O(1) time for _every_ instance, if we can take different constants behind the O-notation for different instances.  That is why the “best-case complexity” in the literal sense is not useful.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-20T14:58:47.160Z
If you're talking about deterministic, non-probabilistic computation, it would take linear time (O(n) time) to check whether two encodings of instances are equivalent: scan the n bits of the input encoding and verify that it is the same as the programmed encoding, no?
Daniel Apon
CC BY-SA 2.5
2010-09-20T15:58:50.717Z
@Daniel: Yes, but if one of the instances is fixed, it only takes constant time, where the constant depends on the length of the fixed instance.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-20T14:42:35.907Z
2010-09-20T14:42:35.907Z
umar
<p>Although I can't quite parse your definitions, you should know that much stronger time hierarchies are known, in particular "almost everywhere" time hierarchies. </p>

<p>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)$.   </p>

<p>"Sufficiently small" means $t(n) \log t(n) \leq o(T(n))$.</p>

<p>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 <em>all</em> inputs past a certain length. This seems to be what you're looking for in your class BestE.</p>

<p>Reference:</p>

<blockquote>
  <p><a href="http://scholar.google.com/scholar?q=%22A+Note+on+Almost-Everywhere-Complex+Sets+and+Separating+Deterministic-Time-Complexity+Classes%22">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)</a></p>
</blockquote>

CC BY-SA 2.5
2010-09-20T17:26:14.860Z
Very well, thanks. I think you quite well understood my question, and your introducing sentence "I can't quite parse your definitions" is just a sign of your modesty :)
Sadeq Dousti
CC BY-SA 2.5
2010-09-20T17:35:41.067Z
Provided I did guess correctly, your definition should be something like: "L \in BestE \iff (\exists c) (\forall M)[(L(M) = L) \Rightarrow (\exists n_0) 
(\forall n > n_0) (\forall x \in \{0,1\}^n)[T(M(x)) > 2^{c|x|})]."
Ryan Williams
CC BY-SA 2.5
2010-09-20T18:15:12.590Z
Yep, you are right. I edited the definition in the last minute, and misplaced some of the quantifiers. I corrected the question based on your definition.
Sadeq Dousti
CC BY-SA 2.5
2010-09-20T17:08:51.370Z
2010-09-20T17:08:51.370Z
Ryan Williams
<p>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?</p>

<p>Another question considers the <em>best case</em> complexity, exemplified below:</p>

<p>Is there a class of (natural) problems whose decision requires <strong>at least</strong> exponential time?</p>

<p>To clarify, consider some <strong>EXP</strong>-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 <em>best case</em> complexity of $L$ is not exponential time.</p>

<p><strong>EDIT:</strong> 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 <em>lower bounded</em> by some function. For instance, define <strong>BestE</strong> 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:</p>

<p>$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|}}]]$</p>

<p>where $T(M(x))$ denotes the times it takes before $M$ halts on input $x$.</p>

<p>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.</p>

<p>Yet notice that the polynomial-time counterpart (<strong>BestP</strong>) is natural, since every Turing machine requires time $|x|$ to at least read its input.</p>

<p>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.</p>

<p>PS2: One can also consider the circuit-complexity counterpart, in which we consider the least circuit size/depth to decide a language.</p>

CC BY-SA 2.5
2010-09-20T12:40:47.323Z
Just because there are instances of SAT that are easy, it doesn't mean that its expected time is polynomial.  I'm not sure I understand your question..
Lev Reyzin
CC BY-SA 2.5
2010-09-20T14:46:48.130Z
@Lev Reyzin: I didn't mean SAT is in expected poly-time. I meant since SAT has easy instances, we cannot say that its "best case" complexity is hard.
Sadeq Dousti
CC BY-SA 2.5
2010-09-20T15:00:17.763Z
Oh, I see, the average case complexity and best case complexity are two separate questions!  Somehow I missed this in my first reading -- my mistake.
Lev Reyzin
CC BY-SA 2.5
2010-09-20T16:58:25.900Z
I can't quite parse your definition of BestE. M and x are sitting outside of their quantification... also, don't you want $M$ to reject inputs which are not in $L$?
Ryan Williams
CC BY-SA 2.5
2010-09-20T18:24:25.510Z
@Ryan: Thanks for pointing out the flaw. I corrected it.
Sadeq Dousti
<cc.complexity-theory><complexity-classes>
Complexity Classes for Cases Other Than "Worst Case"
Sadeq Dousti
# Complexity Classes for Cases Other Than "Worst Case"

(Asked by: username_0 on 2010-09-20)

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.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: Just because there are instances of SAT that are easy, it doesn't mean that its expected time is polynomial.  I'm not sure I understand your question..  
> **username_0**: @username_1: I didn't mean SAT is in expected poly-time. I meant since SAT has easy instances, we cannot say that its "best case" complexity is hard.  
> **username_1**: Oh, I see, the average case complexity and best case complexity are two separate questions!  Somehow I missed this in my first reading -- my mistake.  
> **username_2**: I can't quite parse your definition of BestE. M and x are sitting outside of their quantification... also, don't you want $M$ to reject inputs which are not in $L$?  
> **username_0**: @Ryan: Thanks for pointing out the flaw. I corrected it.  

---

## 5 answers

### Answer by username_2 on 2010-09-20. Score: 15 | Accepted answer

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)](http://scholar.google.com/scholar?q=%22A+Note+on+Almost-Everywhere-Complex+Sets+and+Separating+Deterministic-Time-Complexity+Classes%22)

> **Comments:**
> **username_0**: Very well, thanks. I think you quite well understood my question, and your introducing sentence "I can't quite parse your definitions" is just a sign of your modesty :)  
> **username_2**: Provided I did guess correctly, your definition should be something like: "L \in BestE \iff (\exists c) (\forall M)[(L(M) = L) \Rightarrow (\exists n_0)  (\forall n > n_0) (\forall x \in \{0,1\}^n)[T(M(x)) > 2^{c|x|})]."  
> **username_0**: Yep, you are right. I edited the definition in the last minute, and misplaced some of the quantifiers. I corrected the question based on your definition.  

---

### Answer by username_3 on 2010-09-20. Score: 13

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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:A#avgp)

[HeurP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:H#heurp)

[DistNP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#distnp)

[(NP,P-samplable)](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nppsamp)

[Arora/Barak](http://www.cs.princeton.edu/theory/complexity/) 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](https://cstheory.stackexchange.com/questions/1026/status-of-impagliazzos-worlds).

As far as the "best case" complexity question, I'm not sure I understand quite what you mean. Are you looking for [EXP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#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.

> **Comments:**
> **username_0**: Very well done! That's what I needed for the average-case complexity part of the question. Regarding the "best-case" part, I noticed that the original statement of the question was vague. My bad! I have edited it a lot, so please consider reading it again.  

---

### Answer by username_4 on 2010-09-20. Score: 5

[Expanding on username_2'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](https://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read/1517#1517) 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.)

> **Comments:**
> **username_2**: Actually, his definition only has $M$ accepting inputs in $L$, not rejecting inputs not in $L$... provided you put the condition $M(x)=1$ in the right place.  
> **username_0**: Thanks a lot Joshua. Your answer complements that of Ryan's. Just one edit: In the definition of C-immunity, one "prime" is missing (it should read: no infinite subset $L'$ such that $L' \in C$.)  
> **username_4**: @Sadeq: fixed, thanks.  @Ryan: True (or it was a couple hours ago: he has since updated the definition). Then it would be immunity instead of bi-immunity.  Either way, mainly I just wanted to point out the keyword "immunity."  

---

### Answer by username_5 on 2010-09-20. Score: 2

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 by username_6 on 2010-09-20. Score: -1

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.

> **Comments:**
> **username_7**: I do not think that that counts as a correct algorithm for the problem.  However, your algorithm can be modified so that it first checks whether the input is equal to the particular instance which you have predetermined (in O(1) time).  If it is, it outputs the precomputed answer.  If not, you solve the given instance by any means.  Thinking about it, _any_ correct algorithm runs in O(1) time for _every_ instance, if we can take different constants behind the O-notation for different instances.  That is why the “best-case complexity” in the literal sense is not useful.  
> **username_3**: If you're talking about deterministic, non-probabilistic computation, it would take linear time (O(n) time) to check whether two encodings of instances are equivalent: scan the n bits of the input encoding and verify that it is the same as the programmed encoding, no?  
> **username_7**: @Daniel: Yes, but if one of the instances is fixed, it only takes constant time, where the constant depends on the length of the fixed instance.  

---

