Virtual Gate Test Series: Algorithms - TSP Problem

Question

Comments

Clearly given NP not equal P. So P is a subset of NP.So one can verify TSP problem if some solution is given, but there is no algorithm discovered which solves all instances of this problem.i.e it is polynomially verifiable not polynomially solvable.

Answer 1

I guess C is option.

As Question is saying that Travelling salesman problem lies in NP-Complete class. So it consists of both 1. NP and 2. NP hard class of problems.

NP: Class of problems whose solution can be verified in Polynomial time.

NP-Hard:  A lot of times you can solve a problem by reducing it to a different problem.  I can reduce Problem B to Problem A if, given a solution to Problem A, I can easily construct a solution to Problem B.  (In this case, "easily" means "in polynomial time.")

Since NP complete is intersection of NP and NP hard, means they are reduceble to some form whose solution can easily be given, and with a given solution we can veryfy that if it is correct or not.

Correct me if i am missing something.