# HP researcher claims proof that P != NP

Clive D.W. Feather clive at davros.org
Thu Aug 12 08:19:35 BST 2010

```Ian Batten said:
>> 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.

Indeed. But, as a corollary, travelling salesman is also NP-complete.

There's an incomplete list at:
http://en.wikipedia.org/wiki/List_of_NP-complete_problems

> 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 :-)

Thus proving that WAGN management were not NP-complete. Though getting a
point through to them might well be an NP-hard problem.

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

```