Answered from MIT Professor: What is Strong ETH (Recently Proven False By OpenAI) | Ryan Williams · Ryan Peterman · 2026-10-27
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.
“However, in the worst case, we still don't know how to solve it significantly faster” Ryan Williams · at 1:29 — 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 →