Efficient algorithms, the Exponential Time Hypothesis, and losing the plot

Re:Efficient algorithms, the Exponential Time Hypothesis, an... by karmakurtisaani on Tuesday November 03, 2026 @03:48AM (#50349591)

Yep, ranting against galactic polynomial algorithms reminds me of the people who oppose the use of infinity. Like, yes, it's not physically realistic construction, but it makes things simple enough that we can do analytic solutions to problems and simplify terribly complicated things.

Polynomials are closed under multiplication, so you can do a poly algorithms poly number of times and still have a poly algorithm. That's very convenient.

[ Parent | on HN ]

Re:Efficient algorithms, the Exponential Time Hypothesis, an... by layer8 on Tuesday November 03, 2026 @05:58AM (#50350425)

The article makes the point that not all polynomial algorithms are created equal. If you combine ten O(n^2) algorithms, you can end up with an O(n^1024) algorithm, which suddenly isn’t practical anymore, despite being polynomial. That’s inconvenient.

[ Parent | on HN ]