Does MIT professor Ryan Williams believe the strong exponential time hypothesis is true?

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.

• Williams says he was attacking CNF SAT faster than 2^n early in grad school.
• Restricted versions such as 3-SAT already have algorithms that beat 2^n.

▸In their words

“I think I'm on the record as not believing this hypothesis.” Ryan Williams · at 2:04 — open in the transcript →

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