This is another rant about the author's bugaboo.

It would be great to prove that there is or isn't a non-galactic polynomial-time algorithm for NP-complete problems. But we can't even solve the easier problem of proving there is or isn't a galactic polynomial-time algorithm, so what hope is there for the harder problem?

If you could prove that any polynomial-time algorithm for NP problems had to be galactic, you would be the most celebrated computer scientist since Turing. It's just no one has any idea how to do that.

▲

karmakurtisaani 5 hours ago | parent [-]

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.

	▲	layer8 3 hours ago \| parent [-]
		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 isn’t practical anymore, despite being polynomial. That’s inconvenient.