Dersu

The strong exponential time hypothesis (SETH) explained by MIT professor @rrwilliams who was selected by OpenAI to verify the recent breakthrough result: Q: "Could you explain the Strong Exponential Time Hypothesis, or SETH, and its significance?" Ryan Williams: "Strong ETH is a severe strengthening of the P versus NP question. P versus NP is asking whether the SAT problem has a polynomial-time algorithm or not. Strong ETH is basically saying that for the SAT problem, you cannot solve it much faster than 2^n. There’s no 1.999^n time algorithm. For every string of 9s, there is no 1.9999^n time algorithm. To say it totally precisely, it has to do with the k-SAT problem, where you’re looking at clauses of length k for arbitrary k, but those details don’t matter so much. SAT is a canonical NP-complete problem. It’s solved all the time in practice. It’s extremely useful for verification; nowadays it’s an engine for verification. So it can be solved fairly well in practice. However, in the worst case, we still don’t know how to solve it significantly faster than 2^n. So the hypothesis that it needs, say, 1.99999^n time is a very strong exponential time hypothesis. It’s stronger than P versus NP. It says it’s not just superpolynomial. It’s darn near 2^n time that you need." Q: "Do you think that hypothesis is true? Why or why not?" Ryan Williams: "I think I’m on the record as not believing this hypothesis. Why don’t I believe it? I started thinking about this hypothesis maybe already as an undergrad, but certainly early in grad school. Before it was even called Strong ETH, I guess that shows how old I am. I was trying to figure out how to solve CNF-SAT faster than 2^n. At the time there were a number of other NP-complete problems that had faster algorithms, like subset sum. So I thought, what’s so special about SAT? If all these other problems have faster algorithms, why not SAT as well? Even 3-SAT, where each clause is an OR of 3 variables, has a faster algorithm, and this is just a more general version of SAT. So at first I thought there’s no good reason to believe a lower bound. These other related problems have upper bounds, so why not? But then, over time, I would have different attacks on Strong ETH, always trying to refute it in different ways. These attacks would fail in some completely catastrophic and ridiculous way. They would have no chance of actually solving the original problem. But by staring at my failure, I’d think: there’s something interesting happening here. It doesn’t refute Strong ETH, so what does it do? By trying to pivot and figure out what I could do with my failure, I was able to solve a variety of other problems instead. So after a while, I realized that the truth value of Strong ETH to me is almost irrelevant. If I believe that it’s false, then I get good ideas. By thinking about what an algorithm that breaks 2^n could look like, I force myself to think in a different way. I have to discard the natural algorithmic possibilities, because we know they won’t work, and think in a different direction. Because it sends my brain in a different direction, it’s very useful for research. Even though I still haven’t refuted it, it’s very useful for me to believe that it’s false, operationally." Q: This is a minority opinion, right? Ryan Williams: "Russell Impagliazzo, a good friend of mine who helped propose this, always emphasizes to me: this is a hypothesis. We explicitly did not name it a conjecture. We wanted to put forth a lower bound that would get you to think about it, something a little more controversial than P versus NP or other things people more normally believe. Hypotheses at the edge of our understanding, where we truly don’t know what the answer might be based on our intuition, can be enlightening to think about. That’s one reason why it was proposed. But one reason you might believe Strong ETH is true is that it conveniently implies a lot of other lower bounds. You can reduce SAT to a bunch of problems that seem totally unrelated, like edit distance and various pattern matching problems. They have natural polynomial-time solutions. If you could improve on the algorithms for any of those, you would improve the one for SAT as well, and get something better than 2^n. So believing in it makes a convenient worldview. It shows that all these different textbook algorithms are indeed optimal."