Intellectually Curious

When Exponential Isn’t Inevitable: AI Refutes ETH

4:58

Some computer problems become brutally harder as they grow. The Exponential Time Hypothesis proposed that this explosion was unavoidable for a central logic problem called 3-SAT. OpenAI’s new result overturns that assumption with an algorithm that counts the solutions to fixed-width Boolean formulas in subexponential time, using polynomial space. We unpack what those words mean, why counting…