Ryan Peterman · Ryan Peterman · Transcript & summary by WhipScribe
A five-minute, plain-language account of a central conjecture in complexity theory from a researcher who has spent his career trying to break it.
Tap a chapter to open that moment in the transcript; the link to it is copied for you.
“I think I'm on the record as not believing this hypothesis.” Ryan Williams · at 2:04 — open in the transcript →
“SAT is solved all the time in practice.” Ryan Williams · at 1:14 — open in the transcript →
The strong exponential time hypothesis, usually shortened to SETH or strong ETH, is a claim about the satisfiability problem: that no algorithm can beat brute-force search over all 2^n assignments by any constant in the base, so even 1.9999^n time is out of reach. Ryan Williams frames it as a far sharper version of P versus NP. Where P versus NP only asks whether SAT needs more than polynomial time, strong ETH asserts that it needs nearly the full exponential, and the precise statement is made through k-SAT with clause length growing.
The hypothesis sits awkwardly beside practice. SAT solvers are workhorses of modern verification and handle real instances well, yet nobody knows how to beat 2^n meaningfully in the worst case. Williams first doubted the hypothesis as a student, before it had a name, because close relatives such as subset sum and 3-SAT already had algorithms faster than exhaustive search, and he saw no reason general CNF SAT should be the exception.
The more unusual point concerns how he works. His repeated attempts to refute strong ETH collapsed, often badly, but examining why each one failed handed him techniques that settled other problems. He has come to treat the hypothesis's truth as nearly beside the point: assuming it is false forces him to rule out the obvious algorithmic routes and look elsewhere, which is what makes the belief productive in research even though the refutation has not arrived.
An MIT professor of computer science working in complexity theory, who says he has been trying to refute the strong exponential time hypothesis since grad school and is on record as not believing it.
Ryan Williams, speaking with Ryan Peterman, describes the strong exponential time hypothesis (SETH) as the claim that the SAT problem cannot be solved much faster than 2^n time on n variables. No 1.999^n algorithm exists, nor one for 1.9999^n, for any string of nines. The fully precise version is stated for k-SAT with clauses of arbitrary length k, a detail Williams says matters less than the core idea.
Ryan Williams calls strong ETH a severe strengthening of P versus NP. P versus NP asks only whether SAT has a polynomial-time algorithm; strong ETH goes much further and says SAT needs close to 2^n time in the worst case. If strong ETH holds, P is different from NP, but the reverse does not follow.
No. Ryan Williams says he is on record as not believing strong ETH. His doubt dates to his undergraduate and early graduate years, before the hypothesis had its current name, when he noticed that related NP-complete problems such as subset sum already had algorithms faster than exhaustive search, and he saw no reason general SAT should be different.
Ryan Williams points out that SAT solvers run constantly in industry and are a core engine for verification, handling real-world instances fairly well. Practical success says nothing about the hardest inputs, though: in the worst case, nobody knows an algorithm that is significantly faster than 2^n, which is the gap the strong exponential time hypothesis claims can never be closed.
Ryan Williams says his attacks on strong ETH kept failing in catastrophic and sometimes ridiculous ways, with no chance of solving the original problem. Instead of discarding them, he studied what each failed approach actually did accomplish, and by pivoting on that he was able to solve a variety of other problems.
Ryan Williams says the truth of strong ETH has become almost irrelevant to him. Assuming it is false makes him ask what an algorithm beating 2^n could look like, which rules out the natural approaches already known to fail and pushes his thinking in new directions. He calls the belief operationally useful for research, even though he has not refuted the hypothesis.
Our own transcript of the public episode, with a timestamp about every 90 seconds. Tap a timestamp or the link button on a paragraph to copy a link that opens this page there.
0:00strong exponential time hypothesis, or I see it, you know, S E T H. Um, could you explain that and its significance? Strong ETH is like a severe strengthening of the P versus MP question. So P versus MP is, um, asking whether the SAT problem, um, has a polynomial time algorithm or not. And strong ETH is basically saying that for the SAT problem, you cannot solve it much faster than to the n. So there's no 1.999 to the end time algorithm. For every string of nines, there is no 1.9999 to the end time algorithm. To say the hypothesis totally precisely, it has to do with the K-SAT problem. and you're looking at clauses of length k for arbitrary k, but those details don't matter so much. It's a canonical MP complete problem.
1:14SAT is 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 to the end. So the hypothesis that it needs, say, 1.99999 to the n time for all strings of nines is a very strong exponential time hypothesis. It's stronger than P different from NP. It says, no, no, no, it's not super polynomial. It's actually darn near to the n time that you need. Right. And so do you think that hypothesis is true and why or why not? I think I'm on the record as not believing this hypothesis. Yeah. Yeah. Why don't I believe this hypothesis?
2:16Well, I started thinking about this hypothesis maybe already as an undergrad, but certainly starting in grad school. Like early in grad school, I was thinking about this. So before it was even called Serenity TH, I guess that shows how old I am. I was trying to think about how to solve the so-called CNF SAT problem faster than to the end and well at the time there were a number of other NP complete problems that had faster algorithms like subset sum so I thought well there's not I mean what's so special about SAT like if all these other problems have faster algorithms why not SAT as well? Like if you restrict to the three set problem, like, so this is where you have an end of these clauses.
3:14Each clause has like, is an or of three variables. Some of the variables may be negated. You want to know if there's a way to set all the variables to make all the clauses simultaneously true. There is a faster algorithm for that. But this is a more general version of SAT. So at first I just thought, well, there's no good reason to think in a lower bound. These other related problems have upper bounds. So why not but then um over time i would have different attacks on strong eth like trying to refute it always trying to refute it in different ways these attacks would fail in some completely catastrophic and ridiculous way like um they were like have no chance of actually solving the original problem but by sort of staring at my failure and trying to think well there's
4:15something interesting happening here what can i do with this like there's something interesting yeah it doesn't refute uh the strong eth thing what does it do so by trying to pivot and figure out okay what can i do with my failure i was able to solve a like a variety of other problems instead and so after a while i realized that the truth value of strong eth to me is almost irrelevant like because if i believe that it's false then i get good ideas i get i get good ideas like and so by trying to think about okay what would an algorithm that breaks to the end look like what What could it look like? I sort of force myself to think in a different way. I have to like discard other natural algorithmic possibilities
5:13because we know they won't work. And I have to think in a different direction. And so because it kind of like sends my brain in a different direction, sends me thinking a different direction. And so because it kind of like sends my brain in a different direction, sends me thinking a different way, it's very useful for research. I mean, even though I still haven't refuted it or whatever, like it's very useful for me to believe that it's false, like operationally.