-2
$\begingroup$

Is this statement true?

Optimization TSP problems are known to be NP-hard, as we do not have a minimum cost to compare against, and in order to verify a solution is optimal, we need to iterate across the solution space.

$\endgroup$
1
$\begingroup$

This statement seems quite vague and confused.

NP-hardness is precisely defined, and you shouldn't loosely say "optimization TSP problems" because it doesn't specify the problem(s). In fact, it is not uncommon that seemingly small changes in a problem lead to different complexities.

Further, because NP-hardness is precisely defined, a problem is not NP-hard because "we do not have a minimum cost to compare against", but because for every problem $X$ in NP there is a polynomial-time reduction to the problem in question - by definition.

Finally, the expression "... to verify a solution is optimal, we need to iterate across the solution space" should be fleshed out more precisely. If the claim is "to verify a solution is optimal, we must inspect every possible solution of the search space", this is wrong.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.