News for hackers. Stuff that matters.
Re:Complete Enumeration Arguments Deemed Harmful by thaumasiotes on Tuesday January 12, 2016 @02:13PM (#10889614)
> Even verifying a solution to the problem (Is this sequence of cities the shortest path?) cannot be done in polynomial time.

This is a pretty funny claim to see made about one of the most famous NP-complete problems there is. As thelema314 points out, the usual certificate verifies "is this path shorter than a threshold?".

Re:Complete Enumeration Arguments Deemed Harmful by zardo on Wednesday January 13, 2016 @09:59AM (#10894715)
There are variations of the problem. The optimization version is NP-Hard, the decision version is NP-Complete.