On Thu, May 30, 2013 at 12:12:15AM +0200, KheOps wrote: > This is not the first time such a claim is made, but I just came accross > what looks like to be a serious scientific publication claiming that > they prove that P=NP. > > In simple words, this would mean that problems that are considered as > needing a lot of computational effort to solve may in fact be solvable > with algorithms that need much less computational time than what is > implemented now. If proven true, this would have a particularly high > impact on a huge number of computational problems. I am however not sure > to what extent this would impact cryptography. > > http://arxiv.org/abs/1305.5976
two days old, unknown researcher... probably a crackpot. See the Deolalikar section of http://en.wikipedia.org/wiki/P=NP for the most recent previously heralded attempt. It's not the case that P=NP necessarily has particularly high impact on relevant problems. If the reduction is in O(n^100) it's P but not useful in any reasonable sense. Even if the reduction is fast enough to be practical, applications are often far away. > I'd be glad if anyone with enough skills and access to the paper could > give a first opinion on it :) Shockingly, HN has a reasonable discussion. https://news.ycombinator.com/item?id=5785693 -andy -- Too many emails? Unsubscribe, change to digest, or change password by emailing moderator at [email protected] or changing your settings at https://mailman.stanford.edu/mailman/listinfo/liberationtech
