[threatofrain]

That just means you didn’t encode the information you wanted into the graph.

[viraptor]

There's no "information you wanted" in the plain np-hard version of traveling salesman for example. There's only cost. My point was that things get easier if you have the extra information and aren't solving the plain version anymore.