11
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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.. $\endgroup$
    – Lev Reyzin ♦
    Sep 20, 2010 at 12:40
  • $\begingroup$ @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. $\endgroup$
    – Sadeq Dousti
    Sep 20, 2010 at 14:46
  • $\begingroup$ 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. $\endgroup$
    – Lev Reyzin ♦
    Sep 20, 2010 at 15:00
  • $\begingroup$ 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$? $\endgroup$
    – Ryan Williams
    Sep 20, 2010 at 16:58
  • $\begingroup$ @Ryan: Thanks for pointing out the flaw. I corrected it. $\endgroup$
    – Sadeq Dousti
    Sep 20, 2010 at 18:24

5 Answers 5

Reset to default
15
$\begingroup$

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)

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 :) $\endgroup$
    – Sadeq Dousti
    Sep 20, 2010 at 17:26
  • 2
    $\begingroup$ 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|})]." $\endgroup$
    – Ryan Williams
    Sep 20, 2010 at 17:35
  • $\begingroup$ 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. $\endgroup$
    – Sadeq Dousti
    Sep 20, 2010 at 18:15
13
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Sadeq Dousti
    Sep 20, 2010 at 15:33
5
$\begingroup$

[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.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Sep 20, 2010 at 17:19
  • $\begingroup$ 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$.) $\endgroup$
    – Sadeq Dousti
    Sep 20, 2010 at 17:29
  • 1
    $\begingroup$ @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." $\endgroup$
    – Joshua Grochow
    Sep 20, 2010 at 18:45
2
$\begingroup$

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.
Improve this answer
$\endgroup$
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Sep 20, 2010 at 14:51
  • $\begingroup$ 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? $\endgroup$
    – Daniel Apon
    Sep 20, 2010 at 14:58
  • 2
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Sep 20, 2010 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.