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