Author challenges complexity theory efficiency definition

The author argues that complexity theory's historical reliance on polynomial-time as a definition of efficiency is flawed, highlighting how recently touted subexponential algorithms for NP-complete problems like satisfiability rely on exponential subroutines for all practically conceivable problem sizes. The piece uses this example to illustrate how asymptotic thinking creates 'galactic algorithms' unmoored from the realities of computation. Open article →