Problems that are hard in the best case?

Are there any problems that are hard in the best case? In particular, I was wondering if there are problems that are NP-hard or #P-hard in the best case.

1 Answer

To answer the question, one must first define what is meant by "best case".

One possible definition of "best case" complexity is, what is the running time for the best input? In other words, take the minimum over all instances, of the running time for that instance.

With that definition, there are no decision problems (problems with a yes/no answer) that are hard in the best case. That's because I could write a stupid algorithm that knows how to solve one particular problem instance efficiently (it has the solution for that instance hardcoded) and is slow on all else -- in the best case, this would be efficient.

For instance, consider 3-colorability problem, where given a graph we have to determine whether it is 3-colorable. Let's fix a single graph $G_0$ that we know is 3-colorable. Now consider the following algorithm:

Algorithm:
Input: a graph $G$
1. If $G=G_0$, output "Yes".
2. Otherwise, do something very slow to try to test whether $G$ is 3-colorable.

This algorithm is very slow in the worst case (and typical case), but it is fast in the best case: when the input is $G_0$, it immediately outputs the correct answer. The existence of such an algorithm shows that 3-colorability is easy in the best case.

There was nothing special about 3-colorability that I used there. You can apply the same reasoning to any decision problem (or any problem where the output size is not too long).

In retrospect, that was probably the wrong definition. A better definition would be: for a fixed algorithm, let $T(n)$ denote the minimum over all instances of size $n$, of the running time of that instance. Then, the function $T(\cdot)$ is the best-case complexity of that algorithm (and of course we want to know the minimum over all algorithms, or a suitable lower bound that holds for all algorithms). This prevents hardcoding a single instance, because there will be a different best instance for each $n$. I don't know whether there are any problems that are hard, for this best-case complexity measure.

It's more interesting to look at average-case hardness. While many problems are hard in the worst case but easy on the average case, there are some problems that are both hard on the worst case and hard on the average case. One tool used to prove average-case hardness is random self-reducibility. For instance, the discrete log problem is believed to be hard on the average case. In particular, it is believed to be hard on the worst case, and we can prove that if it is worst-case hard, then it is average-case hard, too, using a random self-reduction.

• You could require a stricter definition of best case. Something that requires an infinite number of "best case" instances, like sorted lists for bubble sort. Then you can't hard-code them all. I guess this could be covered under average case complexity with a suitably chosen input distribution. – adrianN Jun 23 '16 at 7:15
• I agree, we should have one best-case per $n$. I think we'll find suitable trivial instances for most if not all problems, though. – Raphael Jun 23 '16 at 9:13