What is the strong exponential time hypothesis, as Ryan Williams explains 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.

• SAT is a canonical NP-complete problem: decide whether some setting of the variables makes every clause true at once.
• SETH says the brute-force 2^n bound is essentially tight, not merely that SAT is super-polynomial.

Source: our own transcription of the episode. The full conversation is on Ryan Peterman (2026-10-27). Read the whole episode summary →

▸More from this episode