Answered from MIT Professor: What is Strong ETH (Recently Proven False By OpenAI) | Ryan Williams · Ryan Peterman · 2026-10-27
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.
Source: our own transcription of the episode. The full conversation is on Ryan Peterman (2026-10-27). Read the whole episode summary →