HP researcher claims proof that P != NP

[Clive D.W. Feather]

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.

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

Roughly so.

> 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?

You are correct.

To expand on this whole thing:

There are a set of problems that are known to be P. That is, you can
solve these problems in time A*N^B where N is the problem size (e.g. key
length). This is called "polynomial time".

There are other problems that are not known to be P but are known to be
NP. That is, it is not known if there's a polynomial time solution but if
you've found a possible solution you can check it in polynomial time.
One such problem is the "travelling salesman" - given a set of towns and
routes connecting them, find the shortest route that visits all the towns.

Another way to think of NP is to imagine your computer has an additional
instruction "guess the right choice out of this set". If the problem would
be polynomial time on such a computer, it's NP. For travelling salesman,
the NP algorithm is:
    Guess the right town to start at.
    While there are unvisited towns, guess the next town to visit.

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.

If P = NP, then there any problem that can be checked in polynomial time
can be solved in polynomial time.

If P != NP, then some problems can be checked in polynomial time but not
solved in it. These will include all the NP-complete problems.

Even if P != NP, just because a particular problem - other than an
NP-complete one - doesn't have a known polynomial time solution, it doesn't
mean that one might turn up later.

Some problems aren't NP either - they can't be checked in polynomial time.

-- 
Clive D.W. Feather          | If you lie to the compiler,
Email: clive at davros.org     | it will get its revenge.
Web: http://www.davros.org  |   - Henry Spencer
Mobile: +44 7973 377646