[bagels]

I don't think p vs np has anything to do with it, but also, I don't think your maxim is always (but maybe often is) true anyways.

Problem: traveling salesman, solution: one particular path. I think verification that the solution is optimal in this case is exactly the same problem as finding the solution.