HP researcher claims proof that P != NP

[Ian Batten]

On 11 Aug 2010, at 23:33, Clive D.W. Feather wrote:

> David Biggins said:
>> 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.
>
> That's right.

The current view is, I believe, that both factorization and discrete  
logarithms (ie DH) are NP-intermediate. They are NP, in that a  
solution can be checked in P but cannot (seemingly) be generated in P,  
but are not NP-complete, in that providing a solution in P would  
neither prove P=NP nor (equivalently) provide a solution to all other  
NP problems.   The difference between RSA and DH is that although DH  
is equivalent to discrete logarithms and therefore is strongly  
believed to be NP, RSA may have solutions that do not involve  
factorization: there may be attacks on other parts of the derivation  
of the public and private keys from the initial primes which either do  
not involve recovering the primes at all or which recover them other  
than by factorization.

> Within the group NP, there are a set of problems called "NP- 
> complete". If
> any of those actually have a polynomial time solution, then all NP  
> problems
> have one and P = NP. Travelling salesman is NP-complete.

The decision problem that is NP-complete is the weaker "is there a  
tour that is shorter than a given number".   That's clearly much  
easier to check that the tour being the shortest.  If I claim you can  
buy a ticket from Cambridge to London for no more than £X and show you  
a ticket for £X, that's the end of it.  If I claim you can buy a  
ticket from Cambridge to London for no _less_ than £X, so X is a  
minimum, I can't simply show you a proof without a lengthy exercise in  
considering whether season tickets between arbitrary pairs of  
stations, such as Finsbury Park to Liverpool Street, may be involved :-)

ian