Theme 1: Criticism that theory ignores practical performance
Many commenters argue that algorithmic theory often produces “galactic” results that are useless in real systems because they rely on unrealistic assumptions (e.g., unbounded precision, arbitrary constants).
- “If algorithmic theorists don't care about practical performance then why should we care about what they're doing? It's just a strange game they're playing, of no interest to anyone else.” – skybrian
- “Theory with no possible practical relevance is useless, and I think a computational complexity result requiring arbitrary‑precision arithmetic that is impossible to implement using any physical system qualifies.” – modeless
- “Lo and behold, even the theorists you complain about don't see that 'loophole' as a solution, declare victory and go home.” – eru (referring to Levin’s universal search)
Theme 2: Defense of theory’s long‑term value
Others maintain that abstract work is essential; breakthroughs may later enable practical advances, and theory provides the foundation for future innovation.
- “STOC/FOCS/SODA, etc are not about 'doing practical algorithms'. If you want that, you go to ESA, ALENEX, or VLDB/SIGMOD… I don't think it's fair to just shit on theory because they don't do experiments.” – p11p
- “But every so often breakthroughs in theory can be turned into breakthroughs in practice.” – eru
- “You care because Pierre de Fermat 16th century work on modular arithmetic was of ‘no intest to anyone else’ except other theorists but it got to shine in the twentieth century in modern cryptography.” – cpa
Theme 3: Debate over computational models and assumptions
A substantial thread discusses which model of computation (Turing machines, register machines, Blum‑Shub‑Smale, exact complex arithmetic, etc.) is appropriate for analyzing algorithms and whether big‑O analyses can be “exploited” by unrealistic models.
- “Turing machines are good for computability but not great for complexity.” – LPisGood
- “At most you use them for stuff like P vs NP, because Turing machines are 'only' polynomially slower than register machines…” – eru
- “There is, of course, the very rich field of Numerical Analysis which deals with how we actually represent these things in real life, but for a starting point assuming this sort of thing is par for the course.” – agrm (referring to Blum‑Shub‑Smale machines)
- “No, it’s unusual to use Turing machines as the model.” – zeroonetwothree
These three strands—practical relevance versus theoretical purity, the enduring worth of abstract work, and the choice of computational model—dominate the conversation.