Dynamic Programming for TSP

Question

after reading about TSP in wiki, I found it stating DP is a exact algorithm for TSP problem, but I'm confused that if they have a exact algorithm for a problem, should the problem still be classified as NPC? Any answer is appreciated. wiki TSP page

Answer 1

Nitin Gurram's comment is absolutely incorrect.

NP-Complete problems can (and do) have exact algorithms, but all such presently known exact algorithms execute in exponential time, worst case. A naive, but still exact, algorithm for the Travelling Salesman problem is to enumerate every possible travelling salesman route, calculate the length for each one, and choose the smallest. But because the number of such paths increases exponentially with the number of cities, the algorithm takes exponential time to execute. The wikipedia page you point to says as much.

The dynamic programming approach is not quite as bad as a naive approach, and it is another exact algorithm, but it still runs in exponential time worst case.

NP-Completeness does not say that there are no exact algorithms. It means that there are no known exact polynomial time algorithms, along with some other technical complexity theory requirements.

(As a side note, NP-Complete is not the same complexity class as NP. All NP means is that there is a polynomial time verification algorithm, given a solution. NP-Complete is a subset of that set with, as I mentioned, some other technical requirements.)