5 ms·
My definition isn't wrong - NP-hard is a superset of NP. There are problems in NP hard whose solutions can't be verified in polynomial time. Also, you're wrong
by emtel 8y ago
My definition isn't wrong - NP-hard is a superset of NP. There are problems in NP hard whose solutions can't be verified in polynomial time.
Also, you're wrong about being able to verify a solution easily. The decision version of the TSP is NP-complete, which means you can't solve it efficiently unless you can solve NP complete problems. You're confusing _solving_ the decision problem with _verifying a solution_ to the decision problem.
- jeromebaek 8y agoEither we are talking past each other or you are confused. A solution to the decision version of the TSP can certainly be verified in polynomial time.