HP researcher claims proof that P != NP

[Ian Batten]

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/b5f7113e/attachment-0001.htm>