Don't Fall In Love With Your Model: The Cautionary Tale of my Recent proof that P=NP(math.rutgers.edu)
math.rutgers.edu
Don't Fall In Love With Your Model: The Cautionary Tale of my Recent proof that P=NP
http://www.math.rutgers.edu/~zeilberg/Opinion98.html
2 comments
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.)
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.
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.
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.
crackpottery