Theoretical Computer Science is blessed (or cursed?) with many open problems. For some of these questions, such as the vs problem, it seems like it could be decades or more before they reach resolution. So, if we have no proof either way, what do we assume about the answer? We could remain agnostic, saying that we simply don’t know, but there can be such a thing as too much skepticism in science. For example, Scott Aaronson once claimed that in other sciences would by now have been declared a law of nature. I tend to agree. After all, we are trying to uncover the truth about the nature of computation and this quest won’t go any faster if we insist on discarding all evidence that is not in the form of mathematical proofs from first principles.
But what other methods can we use to get evidence for questions in computational complexity? After all, it is completely hopeless to experimentally verify even a non-asymptotic statement such as “There is no circuit of size that can solve 3SAT on variables”. This is the question I’ll focus on in this post. I’ll use as case studies two fascinating conjectures for which, unlike the vs problem, there is no consensus on their veracity: Khot’s Unique Games Conjecture and Feige’s Random 3SAT Hypothesis.
There is in some sense only one tool scientists have to answer such questions, and this is Occam’s Razor. That is, if we want to decide whether an answer to a certain question is Yes or No, we try to think of the simplest/nicest possible world consistent with our knowledge in which the answer is Yes, and the simplest such world in which the answer is No. If, for example, we need to twist and stretch the “No” world in order to fit it with current observations, while the “Yes” world is very natural, and in fact predicts some corollaries that have already been verified, then we can conclude that the answer to our question is probably “Yes”. Let us do this exercise for both of these conjectures.
The Unique Games Conjecture
Khot’s Unique Games Conjecture (UGC) states that a certain approximation problem (known as “Unique Games” or UG) is NP hard. One benefit of using Occam’s Razor is that, if we’re not insisting on formal proofs, we can avoid describing the UG problem and instead focus on the Small Set Expansion (SSE) problem, which I find a bit more natural. While SSE and UG are not known to be formally equivalent, all known algorithmic and hardness results apply equally well to both (c.f., 1, 2, 3, 4, 5, 6). So, whether the UGC is true or not, in a “nice” world these two problems would be equal in computational difficulty. The SSE problem can be described as the problem of “finding a cult inside a social network”: you’re given a graph over vertices, and you know that it contains a set of at most, say, vertices that is “almost isolated” from the rest of the graph, in the sense that a typical member of has of its neighbors also inside . The goal is to find or any set of similar size that is reasonably isolated (say having more than half of the neighbors inside it).
The “UGC true” world.
There is one aspect in which the world where UGC holds is very nice indeed. One of the fascinating phenomenons of complexity is the dichotomy exhibited by many natural problems: they either have a polynomial-time algorithm (often with a low exponent) or are NP-hard, with very few examples in between. A striking result of Raghavendra showed that the UGC implies a beautiful dichotomy for a large family of problems (the constraint-satisfaction problems): there is a clear and simple division between the parameters where they can be solved in polynomial (in fact, quasilinear) time, and those which they cannot. In fact, a single algorithm (based on the Goemans-Williamson semidefinite program for Max-Cut) solves all the cases that can be solved in polynomial time, whereas the rest are NP hard. Alas there is one wrinkle in this picture: where you might expect that in this dichotomy the hard problems would all be equally hard, the subexponential algorithm for unique games shows that some of them would be solved in time for some , while others are widely believed to require (or at least ) time. So, the “UGC True” world will have at least three categories of constraint-satisfaction problems with complexity linear, exponential, and sub-exponential. While those sub-exponential problems are asymptotically hard, compared to “proper” NP-hard problems such as SAT, the instance sizes when this hardness shows up will be pretty huge (e.g., for SSE with the parameters above, the algorithm takes roughly steps which means the input size will need to be at least or so before it’s not efficiently solvable).
Perhaps the most obvious way in which the “UGC True” world is consistent with current knowledge is that we don’t know of any algorithm that efficiently solves the SSE (or UG) problem. However, by this we mean that there is no algorithm proven to solve the problem on all instances. So there has been an ongoing “battle” between papers showing algorithms that work for natural instances, and papers showing instances that fool natural algorithms. For example, the semi-definite program mentioned above solves the problem on random or expanding inputs. On the other hand, it was shown that there are instances fooling this program (and some generalizations), along the way disproving a conjecture of Goemans and Linial. The subexponential algorithm mentioned above actually runs much faster on those instances, and so for a some time I thought it might actually be a quasipolynomial time algorithm, but there exist instances based on the Reed-Muller code that require it to take (almost) subexponential time. The latest round in this battle was won by the algorithmic side: it turned out that all those papers showing hard instances utilized arguments that can be captured by a sum of squares formal proof system, which implies that the stronger “Sum-of-Squares”/“Lasserre” semidefinite programming hierarchy can solve them in polynomial time.
The “UGC False” world.
While the Unique Games Conjecture can fail in a myriad of ways, the simplest world in which it fails is that there is an efficient (say polynomial or quasipolynomial time) algorithm for the SSE and UG problems. And, given current knowledge, the natural candidate for such an algorithm comes from the “Sum-of-Squares” hierarchy mentioned above. Indeed, for a fairly natural problem on graphs, it’s quite mind boggling that finding hard instances for small-set expansion has been so difficult. In contrast, for other seemingly related problems such as Densest -Subgraph, random instances seem to be the hardest case. On the other hand, we already know that random instances are not the hardest ones for SSE, so perhaps those hard instances do exist somewhere and will eventually be found.
There is actually a spectrum of problems “in the unique games flavor” including not just SSE and UG, but also Max-Cut, Balanced Separator and many others. The cleanest version of the “UGC False” world would be that all of these are significantly easier than NP-hard problems, but whether they are all equal in difficulty is still unclear. Perhaps rather than a dichotomy there would be a smooth time/approximation ratio tradeoff between the threshold in which such problems are NP-hard, and the one in which it can be solved in quasilinear time by the variant of the Geomans-Williamson algorithm.
A personal bottom line.
Regardless of whether the UGC is true, it has been an extremely successful conjecture in that it led to the development of many new ideas and techniques that have found other applications. I am certain that it will lead to more such ideas before it is resolved. There are a number of ways that we could get more confidence in one of the possibilities. We could boost confidence in the “UGC True” case by finding instances that require the sum-of-squares hierarchy a long time to solve. Note that doing so would require using new ideas beyond sum-of-squares arguments. Another way to support the UGC is to try to come up with candidate NP-hardness reductions (even without analysis or assuming some gadgets that have yet to be constructed) for proving it, or to show NP-hardness for problems such as Max-Cut that are “morally close” to the UG/SSE questions. On this latter point, there are some hardness results for problems such as 3LIN over the reals, subspace approximation, and subspace hypercontractivity that have some relation to the UGC, but whether they can be thought as “morally close” to UG/SSE in difficulty is still in question. To get confidence in the “UGC False” case we can try to show that the sum-of-squares algorithms succeeds on a larger family of instances. A pet question of mine is to show that it succeeds on all Cayley graphs over the Boolean cube. I think that showing this would require ideas that may enable solving the general case as well. Indeed, my current guess is that the UGC is false and that the sum-of-squares algorithm does solve the problem in a reasonable (e.g., quasipolynomial) time.
Feige’s Random 3SAT Hypothesis
Unlike Khot’s conjecture, Feige’s Hypothesis (FH) deals with average-case complexity. While a counting argument easily shows that with high probability a random 3SAT formula on variables and clauses will not be (even close to) satisfiable, the hypothesis states that there is no efficient algorithm that can certify this fact. That is, any one-sided error algorithm for 3SAT (an algorithm that can sometimes say “Yes” on an unsatisfiable instance, but will never say “No” on a nearly satisfiable one) will (wrongly) answer “Yes” on a large fraction of the input formulas. Feige’s hypothesis (and variants of similar flavor) have been used to derive various hardness of approximation results. Applebaum, Wigderson and I also used related (though not equivalent) assumptions to construct a public-key cryptosystem, with the hope that basing cryptosystems on such combinatorial problems will make them immune to algebraic and/or quantum attaches. We note that while the conjecture was originally stated for 3SAT, it can be generalized to every constraint satisfaction problem. Personally I find the -XOR predicate (i.e., noisy sparse linear equations) to be the cleanest version.
There is added motivation for trying to study heuristic evidence (as opposed to formal proofs) for Feige’s hypothesis. Unlike the UGC, which could be proven via a PCP-type NP-hardness reduction, proving FH seems way beyond our current techniques (even if we’re willing to assume standard assumptions such , the existence of one-way functions, or even the hardness of integer factoring). Thus if Feige’s hypothesis is true, our only reasonable hope is to show this by a physics-like process of accumulating evidence, rather than by a mathematical proof. Let us now try to examine this evidence:
The “FH True” world.
One natural way to refute Feige’s Hypothesis would be to show a (worst-case) approximation algorithm for 3SAT. This is an algorithm that given a formula for which an fraction of the clauses can be satisfied, returns an assignment satisfying of them. In particular, given as input a satisfiable formula, must return an assignment satisfying at least fraction of the clauses. Thus, we can transform into a one-sided error algorithm that answer “Yes” on an instance if and only if returns such a -satisfying assignment for it. Since in a random 3SAT formula, the maximum fraction of satisfiable clauses is very close to , the algorithm would refute FH. However, Hastad’s seminal result shows that 3SAT doesn’t have a -approximation algorithm, hence giving at least some evidence for the “FH True” world.
Feige showed that his hypothesis implies several other such hardness of approximation results, including some not known before to hold under ; deriving such results was Feige’s motivation for the hypothesis. But the connection also works in the other way: verifying the hardness-of-approximation predictions of FH can be viewed as giving evidence to the “FH True” world, particulary when (as was the case in this paper of Khot) the hardness of approximation results were obtained after Feige’s predictions.
Of course, these hardness of approximation results only relate to worst-case version while the average-case could be potentially much easier. We do note however that in many of these cases, these hardness results are believed to hold even with respect to subexponential (e.g. or perhaps ) time algorithms. While this doesn’t imply average-case hardness, it does mean that the set of hard instances cannot be too small. Moreover, the most natural candidate algorithms to refute Feige’s hypothesis- the same sum-of-squares relaxations mentioned above- are known (see also here) not to succeed in certifying unsatisfiability of random instances. Also, as Feige shows, this problem is related to random noisy 3XOR equations, which is a sparse version of the known and well studied Learning Parity with Noise problem (see also discussion here and here).
The world in which the generalized form of FH holds is particularly nice in that there is a single algorithm (in fact, the same Goemans-Williamson semidefinite program from above) that achieves the optimal performance on every random constraint-satisfaction problem.
The “FH False” world.
If Feige’s Hypothesis is false, then there should be an algorithm refuting it. No such algorithm is currently known. This could be viewed as significant evidence for FH, but the question is how hard people have tried. Random -SAT (and more generally -SAT or other CSP’s) were actually widely studied and are of interest to physicists, and (with few hundred variables) are also part of SAT solving competitions. But the instances studied are typically in the satisfiable regime where the number of clauses is sufficiently small (e.g., less than for -SAT) so solutions will actually exist. The survey propagation algorithm does seem to work very well for satisfiable random 3SAT instances, but it does not seem to be applicable in the unsatisfiable range. Survey propagation also seems to fail on other CSPs, including -SAT for .
While not known to be equivalent, there is a variant of FH where the goal is not to certify unsatisfiability of a random 3SAT but to find a planted nearly satisfying assignment of a random 3XOR instance. Such instances might be more suitable for computational challenges (a la the RSA Factoring challenge) as well as SAT solving competitions. It would be interesting to study how known heuristics fare on such inputs.
A personal bottom line.
Unlike worst-case complexity, our understanding of average-case complexity is very rudimentary. This has less to do with the importance of average-case complexity, which is deeply relevant not just for studying heuristics but also for cryptography, statistical physics, and other areas, and more to do with the lack of mathematical tools to handle it. In particular, almost every hardness reduction we know of uses gadgets which end up skewing the distribution of instances. I believe studying Feige’s Hypothesis and its ilk (including the conjectures that solution-space shattering implies hardness) offer some of our best hopes for more insight into average-case complexity. I don’t know if we will be able to establish a similar web of reductions to the one we have for worst-case complexity, but perhaps we can come up with meta-conjectures or principles that enable us to predict where the line between easiness and hardness will be drawn in each case. We can study the truth of such conjectures using a number of tools, including not just algorithms and reductions but also integrality-gap proofs, physics-style analysis of algorithms, worst-case hardness-of-approximation results, and actual computational experiments.
As for the truth of Feige’s Hypothesis itself, while it would be premature to use an FH-based encryption to protect state secrets, I think the current (admittedly inconclusive) evidence points in the direction of the hypothesis being true. It definitely seems as if refuting FH would require a new and exciting algorithmic idea. With time, if Feige’s Hypothesis receives the attention it deserves then we can get more confidence in its veracity, or learn more about algorithms for average-case instances.
Theoretical Computer Science is sometimes criticized for its reliance on unproven assumptions, but I think we’ll need many more of those if we want to get further insights into areas such as average-case complexity. Sure, this means we have to live with possibility that our assumptions turn out false, just as physicists have to live with the possibility that future experiments might require a revision of the laws of nature, but that doesn’t mean that we should let unconstructive skepticism paralyze us. It would be good if our field had more explicit discussion of what kinds of results can serve as evidence for the hardness or easiness of a computational problem. I deliberately chose two questions whose answer is yet unclear, and for which there is reasonable hope that we’ll learn new insights in the coming years that may upend current beliefs. I hope that as such results come to light, we can reach a better understanding of how we can predict the answer to questions for which we have yet no proofs.