Hacker News Reader

Comment by jibiki | Hacker News Reader

The article is (obviously) a joke. But it raises an interesting point about computation (namely, it's a small miracle that practically computable problems are usually those with polynomial time solutions.)

View on HN

Is it really a joke? The guy might actually be the pompous jackass that he appears to be. EDIT: OK, I see it's published on April 1st. :)

We might talk about polynomial time like that's reasonable, but few useful algorithms are worse than X^2 * log x.

After all, the man issue is not the size of the algorithm but how long f(N) takes and all to often we see N > 1,000,000,000 which limits what's reasonable.

Well, okay, but the point is that computing power will catch up to 1b^2 a lot faster than 2^1b.

I think matrix multiplication is O(N^2.71), and there are a few problems in abstract algebra that have doubly exponential algorithms.

Yes, but that is for an N x N matrix. It is more useful to express the complexity in the size of the input, in which case matrix multiplication is N^1.5 or better. (As far as I know, the best known algorithm is pretty close to linear, but it's not known if a linear one exists.)

Matrix multiplication is a great example of this, there has been a lot of research into in sparse matrix multiplication because N^2.71 is still fairly difficult.

Edit: There are a lot of known algorithms that would be extremely useful if they where faster.

I don't think it's that much of a miracle - Cobham's "The intrinsic computational difficulty of functions" covered it pretty well - or least explained the intuition behind why it's a pretty sensible idea - and he (along with Jack Edmonds) pretty much defined the complexity class P.

Reply on news.ycombinator.com