Hacker News Reader

Comment by retsibsi | Hacker News Reader

As I read it, that was sort of their point: if the theorists were blindly focused on Big O complexity, they could 'cheat' by invoking the universal search algorithm as a good-enough solution to a huge class of problems; but they don't, because they're not mindlessly playing a game where Big O complexity is all that matters.

View on HN

The reason universal search doesn't solve big O complexity is that nobody knows the big O complexity of universal search. You want to know the complexity of SAT.

"Ok, here's an optimal SAT algorithm (universal search)".

"Nice, but what is the big O complexity of universal search for SAT?".

"Nobody knows".

You're no better off than before if you wanted an answer like "exponential". On the other hand a provably sub-exponential SAT algorithm would be a huge theoretical breakthrough even if "galactic". Same for a proof that P=NP where the exponent in the P-time SAT algorithm was the 5000th busy beaver number, or whatever.

Agreed.

Also empirically, pretty much any provably polynomial algorithm we have found for anything has fairly tame exponents. That's a big part of why 'polynomial' works as a short-hand for 'tractable' that also has nice theoretical properties.

Btw, I don't know whether the tame exponents are in some sense natural, or whether they are a product of how humans find and design algorithms. Perhaps AI will change that.

Yeah I seem to remember that the earliest known algorithm (Schoof's algorithm) for counting points on an elliptic curve over a characteristic-p field was O(n^8) where n is the bit length of p. But, much more efficient algorithms are known now. I don't know of anything with a higher exponent than 8. The time hierarchy theorem says higher exponents let you solve more problems, but idk if there are natural examples of such problems.

Here's a cool old thread about this topic.

https://cstheory.stackexchange.com/questions/6660/polynomial...

Yes, exactly. I'm afraid I didn't make myself very clear. Thanks for explaining it better than I did.

Reply on news.ycombinator.com