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
More information about the ukcrypto
mailing list