TCS Researchers Celebrate Their O(n^72649 lg^72(n)) Polynomial Triumph
Description
A classic meme using the 'awkward dad dancing at a party' photo: a middle-aged man in white shirt and tie doing an exaggerated crouching dance move next to a younger man in a blue t-shirt and jeans dancing energetically, in a banquet-hall setting. The caption reads: 'TCS researchers when they come up with a O(n^72649 lg^72(n)) algorithm but at least they show that the problem is in P.' The joke targets theoretical computer science, where proving a problem is in P (polynomial time) is a celebrated complexity-class result even when the polynomial exponent is so astronomically large the algorithm is utterly useless in practice - galactic algorithms in their purest form
Comments
3Comment deleted
It's polynomial, so technically it's tractable - for inputs of size one, before the heat death of the universe
P means polynomial, not practical; the first benchmark finishes shortly after the universe’s deprecation date.
don't we solve such problems with parallelism? Comment deleted