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?
Windows On Theory 
Thank you Boaz. Very thought provoking.
I should say (as a side comment) that even from the point of view of Cryptography, there is room to criticize “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.”
During my academic childhood, Cryptographers were much more careful about justifying assumptions and reducing computational assumptions. Over the years, there is a constantly growing trend to assume away the difficult part of the Cryptographer work. I still believe that the wildness of an assumption should be closely correlated to the importance of the result, and I do not get the sense that this is the case.
Amen!
I think all the heuristics people use are sometimes wrong (cryptographers encounter easy problems, and ML/model checkers/economists encounter hard ones) but I find it an interesting question to ask why they even work at all.
I am less concerned with cryptographers using strong assumptions, since we can definitely learn something when they fail, than with people using assumptions that are complicated to state. Alas, at the moment we are unable to get some of our most exciting primitives under simple to state assumptions.
Tags: nitpicking; economics; tangent.
On the whole “Milk on the shelves” = “Nash equilibrium”, I think it’s closer to the truth to say that we’re always in an approximate near-equilibrium and constantly moving towards equilibrium, but simultaneously changes happen which update slightly, or sometimes not so slightly, what the (nearest) equilibrium is.
One simple example is that the announcement of next year’s smartphone alters the equilibrium price of last year’s phone (smart or otherwise). Combine that with similar announcements, plus people moving to a new city, bidding up the rents of everything close to them (including supermarkets, presumably) ever so slightly, and you have the basis for constant adjustments.
“we use a fixed price for milk” — if you had written ‘simple’ instead of ‘fixed’ I’d agree. It is not true that the price is fixed in the sense of ‘held constant’, but it is true that some goods have very few and small price fluctuations. Milk has the characteristics which I think makes this feature likely: it’s traded often in large quantities of small units, and it’s a well-defined and homogeneous product—once you know the fat percentage, whether it’s organic and perhaps brand, each liter of milk is equal to any other liter of milk. The best example of the opposite is housing, or more broadly long-durable consumer assets (cars is a good second example).
By the way, does anyone know whether there are complicated contracts in the housing market? I’m not thinking of the complexity of conducting the transaction (with the aid of realtors) or of financing (which presumably *is* complicated), but rather the trade of one house for one big bag of coins once people agree to trade. I don’t see what ongoing relationships the buyers and sellers could want, except perhaps a warranty (but I suspect the realtors could more beneficially issue those in exchange for a larger commission). Does anyone know?
Thank you. I am very much a non-expert on this, but it seems that economist think people reach a sufficiently good equilibrium that they don’t encounter the computational complexity issues in actuality. Perhaps one can phrase this as
“the market finds the equilibrium, and hence your laptop will find it”.
What evidence do we have that we can generate hard problems at will? The only ones that I can think of are random self-reducibility results, such as for computing the permanent. We have something similar for lattice problems, but we don’t know that SVP or CVP is complete for anything.
Do random k-SAT unsatisfiability threshold results tell us anything about this?
The main evidence is that people (i.e., cryptographers) generate such problems all the time and they seem hard in the sense that people are unable to break them.
Self reducibility results only show that the worst case and the average case complexity are the same – they don’t say whether they’re both easy or both hard.
The threshold results don’t really tell us the problem is hard though they do tell us that the actual satisfiability threshold is bounded away from the threshold where currently known algorithms succeed in finding an assignment.
One example I like about the possibility of generating hard problems “at will” is the following conjecture of Gowers that a random circuit is a one-way function:
Construct a random size O(m) circuit C mapping n bits to n bits by taking m random 3-local permutations (permutations that 3 random indices i,j,k and map (x_i,x_j,x_k) to pi(x_i,x_j,x_k) where pi is a random permutation of {0,1}^3). Gowers conjectured that there is m = poly(n) such that with high probability C would be a one way function. (In fact he went beyond this and conjectured that this would lead to a pseudo-random function family.)
If this conjecture is true (we of course have no way of proving it, but would be nice to try to refute it) then it kind of corresponds to the intuition that a “generic” problem is hard.
SVP and CVP are NP-complete (SVP only under randomized reductions). Admittedly, the worst-case to average-case reductions only work for approximate variants of the problems which are theoretically easier–e.g., they are in co-NP.
My interpretation of the coNP result is that the regime of approximation factors where these problems are NP hard seems qualitatively different from the regime where we have an worst case to average case reduction.
Certainly from a complexity-theoretic perspective, they’re very different beasts. So far, we haven’t found many ways to exploit this algorithmically. But, it’s certainly plausible that we could discover that much faster algorithms exist in this regime.
This is indeed one of my favorite questions – can we use this structure algorithmically in any way? (e.g., even a quantum subexponential algorithm, which actually would be a big deal, since it would mean that if quantum computers are built then our key sizes jump significantly). The other side of this question is whether it is possible to base public key crypto on approximating these problems within a factor of n^{0.499}, which seems to be outside the coNP range.
Hi Boaz,
Yeah.. I’m rather obsessed with that question at the moment. The only algorithm that I know of that exploits this structure at all is the 2^{n/2}-time algorithm for \sqrt{n log n}-SIVP that we buried in [ADRS15]. But, this is a thoroughly unsatisfying example, since we use essentially the same algorithm to solve 2-GapSVP.
For what it’s worth, I believe that all lattice crypto is based on the hardness of approximating lattice problems to within a factor of at least n log n, so we’re quite a bit off from n^{0.4999}.
In this paper https://eprint.iacr.org/2006/444.pdf, Chris Peikert and I showed the existence of a worst-case to average-case reduction based on approximating SVP to within a O(log^{0.5} n) factor for a certain class of ideal lattices.
While for these specific lattices, the corresponding decision problem is in P (and hence there is no contradiction with the coNP results), we still do not know how to exploit the structure of the lattices to solve the approximate search problem.
This fine essay inspired a comment on Shtetl Optimized, which surveys the field-theory literature in regard to reasons why “nature has a bias towards easiness.”
Very nice and thought-provoking essay
“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.)”
This is, of course, a huge subject. On a technical note Market equilibrium is different from Nash equilibrium, although they may be similar hardness issues for market equilibrium. When it comes to Nash equilibrium there are many issues for why we need to be careful in giving it overly descriptive or normative interpretation. There are also serious issues with market equilibrium which are perhaps more basic than its computational hardness.
I agree with John that nature has a bias toward (computational complexity) easiness. So in many natural processes (including economic/social processes) moving from the input to the output represents computation very well below P.
Boaz, I have mulled easiness in nature a lot in recent years (as you know). I think the hardness in crypto requires discreteness somewhere in the definition of the problem: either finite field arithmetic or group theory or lattices.
For real-valued problems, it seems to me if there is no particular reason for the problem to be hard then it is probably not too difficult in practice. To give an example, quadratic programming is too expressive and any freshman can prove NP-hardness. It is going to be difficult in real life. But for many interesting real-life problems it is difficult to prove NP-hardness, and the hardness result seems brittle. (To give an example: PPAD completeness of Nash equilibrium required prizewinning effort, and that hardness result is brittle. One hears the problem is very easy on real life instances.)
I think theoretical CS over-absorbed the hardness lesson from cryptography (certainly I did for many years) e.g., “If we can’t even learn parities with noise, what hope do we have for ML in real life?”
Real life is real-valued. The real-valued version of parities with noise is linear regression; the real-valued version of best low-rank approximation is rank-kSVD, etc. Most intuitions just don’t carry over.
Sanjeev
ps The difficult real-valued problems also appear to be ones that have an element of discreteness in them, e.g. sparse PCA (which I know you have thought about), which also can have a cryptographic flavor.
I am not sure if the issue is “discreteness” vs “real-valued” or something a bit different. It seems that in most cases where real-valued problems are easy, they are solvable (at least heuristically) via local search methods.
I do like your intuition that if you needed to work super hard to get a hardness result, it might mean that you’re not likely to encounter this hardness in the real world. That intuition seems to apply also to discrete problems such as Max-Cut and Unique Games.
It does seem that there are variants of real-valued problems that are hard, and there are also parameter ranges where easy real-valued problems become hard. As one example, in the tensor composition problem (which you worked on) we are able to handle some amount of overcompleteness, but not all the way to the information theoretic bound. In particular as far as I know the problem of decomposing a 3-tensor dimension n of rank, say, n^{1.6}, has no efficient algorithm, despite the fact that this is still identifiable up to rank roughly n^2.
I have no doubt some real-valued problems are difficult. “Discreteness” is not well-defined for sure. My main point was that intuition from crypto is of little help in thinking about hardness for such problems, and gave examples of classic hard discrete problems (very simple ones) whose real analogs are easy.
Another point I forgot to make is the issue of “nonproper” solution.
I have seen some beautiful experiments by Nati Srebro (possibly with coauthors) demonstrating that finding a size k neural net —when we know the data can be classified by such a neural net– can be quite hard for existing algorithms, but finding a neural net of size k^3 (say) is much easier.
Now, traditional generalization theory would say that the neural net of size k^3 is probably going to overfit and thus useless. But for some mysterious reason in the experiments no overfitting happens.
So how should we define a good enough solution?
In your example of tensor decomposition, maybe one never needs to go to that level of overcompleteness. (For dictionary learning it is certainly the case that overcompleteness beyond \sqrt{n} may not make sense…) So sometimes problems may be hard precisely in parameter ranges when they are of little use in practice. I don’t know if this is the case for tensor decomposiition.
Anyway, it is great you are raising the question about difficulty of real-valued problems. Lots of mysteries here, and I sure hope more theorists look at this.
Your suggestion that problems become hard when they are useless is very interesting. If that’s the case (and that’s a big if), I do wonder if there is a deeper reason for this.
One such reason could be what I suggested – that much of ML is about doing things that humans do (e.g., understanding images, language, etc..) and hence these are problems that we know are computationally easy in principle. (And in fact, in some of these cases, we believe that humans are doing this using neural nets that have been learned by the local search algorithm that is evolution.) But perhaps that are other forces at play.
Boaz, I think you inverted my implication (probably you understood correctly but I want to clarify for other readers). I am suggesting that real valued problems can sometimes be hard in parameter ranges where they are not useful. But often there may be other natural condition on inputs which make them easy even in the hard ranges, so it is not an if and only if. (I am thinking for instance of our separability assumption which makes Nonnegative matrix factorization easy).
Our field has been v. focused on proving hardness (and I wasn’t immune to it), and the spectacular successes of crypto theory certainly fed that drive. But maybe the world isn’t so hard, at least some of the time.
And toy discrete problems like k-sat are probably not the right laboratory for studying this issue.
There is a big selection effect here. Usually the problems we look at it will generally be ones at the current frontiers of hardness. If they are too easy or too hard, we don’t spend time thinking about them.
A similar “anthropic” point of view explains the price of milk. Is the price of milk set according to the NE? No, but hiring a consultant to figure out how to improve its price would probably cost more than it’s worth.