Ryan Peterman
Assuming the Strong Exponential Time Hypothesis is false forces researchers away from standard methods, producing mathematical breakthroughs from failed refutations regardless of whether the conjecture is ultimately true.
AI-assisted summary of MIT Professor: Why Contrarian Thinking Improves Your Thoughts | Ryan Williams — original source. Check the original for full context.
Source published:
Key ideas
- The Strong Exponential Time Hypothesis (SETH) represents a severe strengthening of P vs. NP, conjecturing that general CNF-SAT cannot be solved in (2 - ε)^n time for any constant ε > 0. (0:00)
- MIT Professor Ryan Williams remains on record as skeptical of SETH, motivated by known algorithms beating 2^n on related NP-complete problems like Subset Sum and 3-SAT. (1:58)
- Williams treats disbelieving SETH as an operational forcing function, using failed algorithmic attacks to discover mathematical structures that resolve other major open problems in complexity theory. (3:44)
Detailed notes
## Background Published by Ryan Peterman on YouTube on October 27, 2026, this video features an interview clip with MIT professor and Gödel Prize winner Ryan Williams, exploring theoretical computer science and algorithmic thinking following a broader discussion on interview problems.
## TL;DR In this discussion, theoretical computer scientist Ryan Williams breaks down the Strong Exponential Time Hypothesis (SETH), which posits that general CNF-SAT cannot be solved faster than brute-force search around 2^n time. Williams shares his longstanding skepticism toward the conjecture, noting that known faster-than-brute-force algorithms for 3-SAT and Subset Sum suggested that general SAT might also be beatable. Although his direct attempts to refute SETH repeatedly failed in catastrophic ways, examining the mechanisms behind those failures yielded breakthrough techniques that resolved other major open problems. Ultimately, Williams argues that assuming SETH is false serves as a vital operational forcing function that propels his research toward non-obvious ideas.
## Atmosphere & style The conversation carries an intellectually playful, reflective, and candid tone. Host Ryan Peterman guides the exchange with targeted theoretical prompts, allowing Williams to speak with self-deprecating humor about his age and his 'catastrophic' failed attempts at breaking complexity barriers. Watching it feels like listening to a world-class mathematician demystify high-level research, transforming rigid computational boundaries into an engaging philosophical lesson on the creative value of contrarian failure.
## Bulletin - [00:00](https://www.youtube.com/watch?v=LRVprar87W0&t=0s) The Strong Exponential Time Hypothesis (SETH) represents a severe strengthening of P vs. NP, conjecturing that general CNF-SAT cannot be solved in (2 - ε)^n time for any constant ε > 0. - [01:58](https://www.youtube.com/watch?v=LRVprar87W0&t=118s) MIT Professor Ryan Williams remains on record as skeptical of SETH, motivated by known algorithms beating 2^n on related NP-complete problems like Subset Sum and 3-SAT. - [03:44](https://www.youtube.com/watch?v=LRVprar87W0&t=224s) Williams treats disbelieving SETH as an operational forcing function, using failed algorithmic attacks to discover mathematical structures that resolve other major open problems in complexity theory.
## Key takeaways - [00:00](https://www.youtube.com/watch?v=LRVprar87W0&t=0s) SETH strengthens the P vs. NP question by claiming general SAT is not just super-polynomial, but essentially requires brute-force 2^n time in the worst case. - [00:35](https://www.youtube.com/watch?v=LRVprar87W0&t=35s) The formal formulation of SETH is defined over k-SAT as clause length k grows arbitrarily large. - [01:00](https://www.youtube.com/watch?v=LRVprar87W0&t=60s) A stark divide exists between theory and practice: modern SAT solvers efficiently handle industrial software and hardware verification, yet theoretical worst-case bounds remain bounded near 2^n. - [02:08](https://www.youtube.com/watch?v=LRVprar87W0&t=128s) Williams began attempting to beat the 2^n bound for general CNF-SAT during his undergraduate and early graduate school years, before SETH was formally named. - [02:34](https://www.youtube.com/watch?v=LRVprar87W0&t=154s) Non-trivial algorithms already beat naive exhaustive search for other NP-complete problems, such as Subset Sum. - [02:44](https://www.youtube.com/watch?v=LRVprar87W0&t=164s) Restricting clause length to three literals in 3-SAT allows algorithms to run strictly faster than 2^n, prompting Williams to question why general SAT should have a rigid 2^n lower bound. - [03:44](https://www.youtube.com/watch?v=LRVprar87W0&t=224s) Williams's repeated attempts to refute SETH routinely failed in catastrophic and absurd ways on the target SAT problem. - [04:00](https://www.youtube.com/watch?v=LRVprar87W0&t=240s) By deeply analyzing the mechanics of catastrophic failures, Williams repurposed broken techniques to solve entirely different open problems in theoretical computer science. - [04:18](https://www.youtube.com/watch?v=LRVprar87W0&t=258s) Williams views the actual truth value of SETH as secondary to the generative value of believing it to be false. - [04:32](https://www.youtube.com/watch?v=LRVprar87W0&t=272s) Assuming SETH is false acts as a cognitive forcing function, instantly ruling out conventional algorithmic ideas and directing thought toward non-obvious paradigms. - [05:12](https://www.youtube.com/watch?v=LRVprar87W0&t=312s) Contrarian belief can serve as an exceptionally productive research heuristic even in the absence of an ultimate proof or refutation.
## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=LRVprar87W0&t=0s) Understanding the Strong Exponential Time Hypothesis (SETH)
Ryan Peterman introduces the topic by asking Ryan Williams to explain the Strong Exponential Time Hypothesis (SETH) and why it holds such significance in theoretical computer science. Williams frames the concept by contrasting it directly with the field's most famous open problem: “Strong ETH is like a severe strengthening of the P versus NP question.” While $P \text{ vs } NP$ fundamentally asks whether the Boolean satisfiability problem (SAT) can be solved in polynomial time or not, the Strong Exponential Time Hypothesis makes a far more drastic assertion. SETH posits that general SAT cannot be solved significantly faster than brute-force search—specifically, that there is no algorithm running in $O(1.999^n)$ time, or $(2 - \varepsilon)^n$ for any constant $\varepsilon > 0$, no matter how many nines one appends after the decimal.
Williams explains that a completely precise formulation of the hypothesis is stated in terms of the $k$-SAT problem, where one considers Boolean formulas in conjunctive normal form with clauses of length $k$ as $k$ grows arbitrarily large. In practical domains, SAT is ubiquitous; Williams points out that modern SAT solvers work remarkably well on real-world inputs and function as an essential engine for industrial software and hardware verification. However, theoretical computer science focuses on worst-case complexity, and in that worst-case setting, nobody knows how to beat $2^n$ search time in general. Contrasting it once more with standard complexity bounds, Williams emphasizes the sheer extremity of the conjecture: “It says that no no no no, it's not super polynomial. It's actually darn near 2 the n time that you need.”
- **P vs. NP baseline:** Asks whether SAT has a polynomial-time algorithm ($P = NP$) or requires super-polynomial time ($P \neq NP$). - **SETH assertion:** In the worst case, general CNF-SAT cannot be solved in $(2 - \varepsilon)^n$ time; for any fixed string of decimals like $1.9999\dots$, no algorithm exists that scales bounded away from $2^n$. - **Real-world vs. theoretical divide:** Despite worst-case exponential hardness, specialized heuristics solve industrial SAT instances efficiently every day for verification and automated reasoning.
---
[01:58](https://www.youtube.com/watch?v=LRVprar87W0&t=118s) Doubting SETH: Early Intuitions and the 3-SAT Contrast
When Peterman asks whether he personally believes the hypothesis to be true, Williams admits his skepticism: “I think I'm on the record as not believing this hypothesis.” He recounts that his fascination with beating $2^n$ began long before the conjecture even had its current name, thinking back to his days as an undergraduate and the early stages of graduate school—quipping that this timeline “shows how old I am.” At that time, he was actively trying to find faster algorithms for general CNF-SAT because standard intuition from other NP-complete problems suggested room for improvement.
Williams notes that several canonical NP-complete problems had already yielded non-trivial algorithms that beat naive exhaustive search, such as Subset Sum. Furthermore, restricted variations of satisfiability itself were already known to be solvable strictly faster than $2^n$ time. In 3-SAT, where each clause is restricted to a disjunction of at most three literals (variables or their negations) conjoined together, specialized algorithms successfully break the $2^n$ barrier. Williams reasoned that if 3-SAT and other related NP-complete problems allowed for faster-than-brute-force upper bounds, there was no foundational reason to assume general SAT was burdened with such a rigid lower bound.
```mermaid flowchart TD accTitle: Williams's Skepticism Toward SETH accDescr: Flowchart contrasting known upper bounds in NP-complete problems against the assumption of SETH hardness. subgraph KnownUpperBounds["Known Faster Algorithms (< 2^n)"] A["Subset Sum"] B["3-SAT (< 2^n algorithms exist)"] end subgraph SETHConjecture["SETH Lower Bound Claim"] C["General CNF-SAT requires ~2^n"] end KnownUpperBounds -.->|"Contradicts natural intuition"| D["Williams's Initial Skepticism:<br/>'Why should general SAT be so special?'"] SETHConjecture -.-> D ```
---
[03:44](https://www.youtube.com/watch?v=LRVprar87W0&t=224s) The Productive Power of Catastrophic Failure and Contrarian Belief
Williams recounts how his attempts to disprove SETH shaped his entire research methodology. Over the years, he launched numerous attacks aimed at refuting the hypothesis by constructing faster algorithms. Invariably, these attempts collapsed: they would fail in what he describes as “some completely catastrophic and ridiculous way” that left zero hope of solving the original SAT problem. Rather than abandoning the wreckage, Williams developed the habit of staring deeply into the failed mechanics, asking what peculiar phenomenon was actually occurring beneath the surface. By pivoting and repurposing the salvageable mathematical structures from those failures, he repeatedly discovered that the broken techniques could solve entirely different, previously open problems.
Through this cycle, Williams arrived at an unconventional philosophy: the objective truth or falsity of SETH is practically secondary to the generative power of disbelieving it. He explains that assuming the hypothesis is false serves as a powerful operational forcing function: “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.” Because all obvious, conventional techniques are already proven incapable of beating $2^n$, setting out to break the barrier forces him to discard standard approaches immediately and steer his thoughts in non-obvious directions. Williams reflects that even without an ultimate refutation in hand, contrarian optimism remains his most potent research engine: “I mean, even 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.”
```mermaid flowchart LR accTitle: Williams's Contrarian Research Heuristic accDescr: Diagram illustrating how assuming SETH is false leads to failures that unlock breakthroughs in other problems. subgraph Heuristic["Contrarian Hypothesis"] A["Assume SETH is False"] --> B["Force Brain Away from<br/>Standard Algorithmic Ideas"] end subgraph Execution["Attack & Pivot"] B --> C["Attack CNF-SAT (< 2^n)"] C --> D["Catastrophic Failure on SAT"] D --> E["Stare at Mechanics of Failure"] E --> F["Solve Other Major Open Problems"] end ```
- **Embracing failure:** Unsuccessful refutations of SETH yielded mathematical insights that solved other foundational problems across computational complexity. - **Cognitive forcing function:** Assuming SETH is false eliminates ordinary proof paths that are known dead ends, compelling the researcher to invent alternative paradigms. - **Operational utility:** A hypothesis can function as a productive intellectual tool regardless of whether it is ultimately proven true or false.
## Notable quotes > [03:44](https://www.youtube.com/watch?v=LRVprar87W0&t=224s) 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. — Ryan Williams
> [00:00](https://www.youtube.com/watch?v=LRVprar87W0&t=0s) Strong ETH is like a severe strengthening of the P versus NP question. — Ryan Williams
## Mentioned Ryan Williams, Ryan Peterman, Strong Exponential Time Hypothesis (SETH), P vs NP, Boolean satisfiability problem (SAT), 3-SAT, k-SAT, Subset Sum, Gödel Prize, Massachusetts Institute of Technology (MIT)
## Video description Ryan Williams is a professor at MIT and the winner of the Gödel Prize in theoretical computer science. I interviewed him all about his work starting by asking him a popular Leetcode question (3 SUM).
Watch the full conversation: https://www.youtube.com/watch?v=AaK1SL2i_4Y
[Source](https://www.youtube.com/watch?v=LRVprar87W0)