Re:A prophet will arise in CS
by anamax on Monday May 09, 2011 @06:29PM
(#2530472)
> You don't think it's exciting that we can show that we can show that routing FedEx trucks, scheduling university final exams, and finding mathematical proofs are, in a very strong mathematical sense, the exact same problem (NP-Completeness)?
I think that it's exciting, but it's not generally exiting.
> That if someone at FedEx could came up with an efficient way of finding the shortest paths for their trucks to follow, they would in the process have broken all modern cryptography
Slow down there there cowboy. Polynomial time is not enough. You need a reasonable constant factor and a small-enough degree.
To put it another way, N2 is too slow at Google-scale. (Actually, N lg N is too slow for some of their problems.)
I think that it's exciting, but it's not generally exiting.
> That if someone at FedEx could came up with an efficient way of finding the shortest paths for their trucks to follow, they would in the process have broken all modern cryptography
Slow down there there cowboy. Polynomial time is not enough. You need a reasonable constant factor and a small-enough degree.
To put it another way, N2 is too slow at Google-scale. (Actually, N lg N is too slow for some of their problems.)