> If we solve NP-complete efficiently then we may break TSP and all sorts of magical optimisation problems joyously drop out of the sky at our feet. It is not clear if this would also break integer factorisation and thus RSA, but perhaps it might.<p>Not true. Factorization is NP, so having a fast way of solving NP-complete problem would yield a way to solve factorization as well.
On the contrary it is not known to be NP-complete (and is believed to not be), so solving factorization in polynomial time would not help with other NP problems.
No, for the reason outlined by Aaronson in [0] - I don't see anything in the update which addresses this.<p>[0] <a href="http://www.scottaaronson.com/blog/?p=2212" rel="nofollow">http://www.scottaaronson.com/blog/?p=2212</a>
This article says nothing. It waffles vaguely about a number of unrelated topics, adding nothing of value to anything that's been said previously, and critically adding nothing of value to the paper it links to.<p>I suspect it is on the front page of Hacker News only because no-one else wants to appear ignorant of the topics in question by pointing out that it makes no sense.
No. Grab a copy of Ja Ja's book. There are some cool things you can do with a PRAM machine. <a href="http://www.amazon.com/Introduction-Parallel-Algorithms-Joseph-JaJa/dp/0201548569" rel="nofollow">http://www.amazon.com/Introduction-Parallel-Algorithms-Josep...</a>