HP researcher claims proof that P != NP

[Clive D.W. Feather]

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