[liberationtech] P=NP ?

[Andy Isaacson]

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