Wait, does this mean "hard" refers merely to worst-case complexity, not to average-case complexity?
Which would seem strange, since, intuitively, a hard worst-case means just that the problem is "possibly hard".
Which would seem strange, since, intuitively, a hard worst-case means just that the problem is "possibly hard".
For SAT, you can sort of correlate difficulty with the number of irreducible clauses.
The reason why its not studied as much by theoretical computer science as is by algorithm-implementers, is that "average" is not uniquely defined. For instance, you can talk about the uniform distribution for a lot of problems, but not always. Suppose you want to investigate the complexity of solving certain types of equations, involving matrices as unknowns. How do you take the uniform distribution over matrices over the (infinite) real numbers? In principle, there are technical definitions you can make [3], and [2] has some results about this, but at the end of the day, there is no objectively superior way of doing it.
What this all leads to are two questions. (1) Would studying average-over-some-sampling-distribution-case complexity yield insights on what is computation? I don't know.
(2) Is it practically useful to classify problems in this way? Not really. Because in the real world, your distribution will rarely be uniform, so it is far better to optimize your algorithms for the distribution you do get.
[1] https://en.wikipedia.org/wiki/Average-case_complexity
[2] https://arxiv.org/pdf/cs/0606037.pdf
[3] https://mathoverflow.net/questions/76295/intuition-for-haar-...
> Note that it is not desirable for the candidate function to be NP-complete since this would only guarantee that there is likely no efficient algorithm for solving the problem in the worst case; what we actually want is a guarantee that no efficient algorithm can solve the problem over random inputs (i.e. the average case). In fact, both the integer factorization and discrete log problems are in NP ∩ coNP, and are therefore not believed to be NP-complete.
Regarding this question:
> How do you take the uniform distribution over matrices over the (infinite) real numbers?
Well, naively, how about screw the real numbers and just take the uniform distribution over the, say, 64 bit floats, which are conveniently finite? At least if we use those in practice? But I guess this goes in the direction of "Because in the real world, your distribution will rarely be uniform", since the 64 bit floats are a subset of the real numbers, and any uniform distribution over the former is equivalent to a non-uniform distribution over the latter (probability 0 to any reals not in the 64 bit floats).
Complexity theory is a very subtle science.