Is computational hardness the rule or the exception?
As a cryptographer, I am used to the viewpoint that computational problems are presumed hard unless proven otherwise. We cryptographers constantly come up with new hardness assumptions, and generally use the heuristic that if a problem doesn’t have an obvious algorithm then it must be hard. We’ve had some interesting failures (see here for a recent example), but this heuristic seems to be successful more often than not.
In most other fields of study, people have the opposite intuition. Algorithms researchers are generally in the business of solving problems, and not giving up any time the obvious approach doesn’t work, and so take the viewpoint that a problem is presumed easy unless it is proven hard. In other fields people seem to take it a step further and claim that a problem is easy even if it is proven to be hard. People working on SAT solving and model checking solve SAT instances on a regular basis, leading some of them to claim that SAT is easy in practice. Similarly, many problems in machine learning are NP hard, but are yet solved all the time by current heuristics (see here for more).
While finding a Nash equilibrium is considered a hard computational problem, economists like to point out (as Eva Tardos told me recently) that there is milk on the shelves in stores, which means that producers and consumers managed somehow to come to an equilibrium where the market clears. (Interestingly, it seems that the process in which people do so is not far from the same heuristics used in machine learning.)
One could say that cryptography is the outlier because the instances there are designed to be hard. Perhaps hardness is this rare phenomenon that needs to be searched for, and P equals NP for “natural” instances. On the other hand, by counting arguments a priori we would expect a “random” or “generic” problem to be hard. Moreover, perhaps in those other fields the problems are designed to be easy. After all, when we use SAT to do model checking, we do so to verify the correctness of a system that was in fact designed by some human to be correct, and would perhaps have been verifiable (with a lot of effort) by a human as well. So perhaps it’s not so surprising that algorithms are able to mimic this reasoning. Similarly, machine learning is mostly about trying to do tasks that humans already succeed in. One could also argue that as a society we design rules that would make achieving equilibrium tractable, and perhaps for this reason we use a fixed price for milk as opposed to some complicated contracts.
So is hardness the rule or the exception? I don’t really know. Perhaps the physicists should decide, as the problems they study come from nature, who presumably doesn’t have any bias toward hardness or easiness. Or does she? After all, nature needs to compute as well (at least in the forward direction). Random constraint satisfaction problems, such as random 3SAT, seem to be a meeting point for physicists, computational complexity folks, cryptographers, and more, and a recent paper makes some algorithmic progress on 3SAT, though it does seem to still be bounded away from the threshold, and it is possible the algorithmic picture clarifies for kSAT and kXOR as k grows.
What do you think?