HP researcher claims proof that P != NP
Ian Batten
igb at batten.eu.org
Wed Aug 11 22:51:42 BST 2010
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>
More information about the ukcrypto
mailing list