YHK - yet another hacker news clone

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

27 points sebg 2 days ago 8 comments

perching_aix 1 hour ago | parent

Author is a math professor who somehow wants you to believe that he didn't know what a computational model is until OpenAI's manuscript dump a few days ago. In this post, he now extends that pretending game to galactic algorithms.

Very gonzo, but maybe I prefer to learn about these things with a little less circlejerk.

traes 1 hour ago | parent

Post #1,000,037 complaining about AI in math by ragging on the existence of pure math. Sigh.

QuesnayJr 1 hour ago | parent

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.

calf 1 hour ago | parent

I don't think the author's criticism of "Big-O Cabal" is very nuanced, but to the second half of the essay it is funny/concerning/sobering to find that the OpenAI proof is doing brute-force search for all instances below some super-astronomic threshold. It kind of buries the lede if the proof did not mention this clearly and the author has to comb through it to find out (I asked ChatGPT the same on the pdf file, but it came up with some other threshold number).

npinsker 26 minutes ago | parent

I don't think it matters? It's completely standard for "galactic" algorithms and not relevant to big-O runtime.

The complaint that these algorithms aren't "realistic" is ostensibly valid, but you could just as well aim that cannon at 95%+ of math research too. Complexity theory is interesting and fun. Isn't that enough?

choeger 37 minutes ago | parent

Would be great to get at least a glimpse of an understanding about why the algorithm does the enumeration in the first place.

Surely it cannot be necessary for the complexity result?!

yorwba 23 minutes ago | parent

It's just irrelevant for big-O complexity what happens for instances below a constant threshold, so the algorithm uses the simplest approach and moves on. If you have an exponential-time algorithm that's faster than brute force for small instances, you can use that and get a faster overall runtime at the same big-O complexity. If you can lower the switchover threshold, ditto. It's a bit weird to dismiss the subexponential algorithm just because it's leaving an obvious optimization on the table... it can only get faster from here.

imtringued 19 minutes ago | parent

Well, since no one has sided with the author, let the math coin clipping keep going without pause.