Search Mailing List Archives
[liberationtech] P=NP ?
adi at hexapodia.org
Wed May 29 16:01:53 PDT 2013
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.
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.
More information about the liberationtech