Three new discoveries in mathematics, computer science, and physics
⚡ INAPP
A preprint dropped on GitHub last week claims to kill the Exponential Time Hypothesis. Specifically, it describes a deterministic algorithm for exactly counting the satisfying assignments of Boolean formulas, which would run in sub-exponential time. If that holds up, it's a genuine shock to complexity theory. If it doesn't, it's still a useful reminder of how slippery these lower bound proofs can be. People keep asking whether this means P equals NP. It doesn't, at least not directly. ETH is a weaker conjecture than P versus NP. It says that 3-SAT can't be solved in time significantly better than 2^n, where n is the number of variables. P versus NP asks whether it can be solved in polynomial time. Breaking ETH cracks the wall between "hard" and "impossible," but it doesn't tear it down. Still, ETH has been treated as bedrock for nearly two decades. Most researchers believed it. A result that falsifies it doesn't just add a new theorem....