Efficient algorithms, the Exponential Time Hypothesis, and losing the plot
Summary
The article critiques how 'efficiency' is defined in computer science, tracing the historical shift from polynomial-time ideals to exponential-time thinking and the ETH. It scrutinizes OpenAI's claim of a subexponential algorithm for SAT, arguing that such results can mislead about practical efficiency and that P vs NP questions may be misframed by 'galactic' scales. The piece offers a perspective on how theory and practice diverge in AI and algorithm design and emphasizes careful interpretation of breakthroughs.