HP researcher claims proof that P != NP

[David Biggins]

Sorry about the top-post reply, but Outlook is playing me up a bit...

 

Excellent, many thanks Ian.

 

So again to just push this for us non-mathematicians,  the various
articles appearing that are talking in terms of this having an impact on
RSA-type crypto are wrong (as my post was) on two grounds:

 

1)  It is not yet certain that crypto is not P.

 

2) It is not certain that even if it is not P, it is actually
permanently "hard" as our understanding of the maths evolves.

 

Am I right still in thinking that even if it is permanently hard as a
deterministic problem, this would not in any way preclude a
probabilistic one?

 

D

 

 

 

 

From: ukcrypto-bounces at chiark.greenend.org.uk
[mailto:ukcrypto-bounces at chiark.greenend.org.uk] On Behalf Of Ian Batten
Sent: 11 August 2010 22:52
To: UK Cryptography Policy Discussion Group
Subject: Re: HP researcher claims proof that P != NP

 

 

On 11 Aug 2010, at 21:59, David Biggins wrote:





So if factoring a large number that is the product of two primes, to get
back the factors,  is a problem that is NP

 

 

Factorisation (or its decision equivalent, more precisely) is in NP and
co-NP, but it's not known if it's in P.  It almost certainly isn't
NP-complete, which means that if tomorrow someone were to produce a P
algorithm for factorization, it wouldn't say anything about P=NP, unless
factorization were proved to be NP-complete, which seems unlikely.  

 

But this is all slightly incidental, because just because something is
in NP doesn't mean it's hard in a practical sense, rather than a
theoretical sense.  It's perfectly possible to have tractable solutions
for practical sized problems in harder complexity classes than P whilst
not having tractable solutions for equivalently sized P problems.  If
you can verify in O(n) but only solve in O(n^100) it's still in P, but
is probably very hard in reality; if you can verify in O(n) but solve in
O((1+epsilon)^n) for a suitably small n we're in NP, but it may in
practical terms be a lot easier to deal with.  There are bigger threats
to factorization as the basis for security than the (highly unlikely)
proof that P=NP, and even if P were to be found to equal NP that
wouldn't actually provide P-time algorithms for factorization.
Conversely, a very efficient factorization algorithm wouldn't say much
about P=NP.

 

ian

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.chiark.greenend.org.uk/pipermail/ukcrypto/attachments/20100811/4ce306d0/attachment-0001.htm>