Given that the traveling sales person problem has been proven to be NP-Complete,

Question

Given that the traveling sales person problem has been proven to be NP-Complete, what does that mean in terms of your writing a program to find the minimal tour for our imaginary travelling salesperson? Explain your reasoning

(a) No problem, just enumerate all possible tours and remember the lowest cost tour. After all we wrote that program this term.

(b) If we have a significant number of cities (say 100) we can never find an optimal solution so, why bother to program the problem.

(c) If we have a significant number of cities (say 100) we can never find an optimal solution so, we should choose one of the many heuritics that allow getting a low cost tour but do not guarantee a minimal cost.

(d) I should dedicate my life (as many have) to finding a minimal cost solution in polynomial time, thus proving that P = NP and thus become famous, all the while giving credit to UNT for the education that made this task (and my life mission) possible.

(e) Tell our imaginary salesperson to set up an online store and stop travelling so much

Explanation / Answer

Travelling sales person problem concerned with finding the shortest hammiltonian cycle in a weighted graph,

it is not in NP because it is not NP.

it's not a decision problem, of course you are translate into a descision problem, but even the translation which ,

I believe, would appeal as the most natural for a lot of people is not verifiable in polynomial time unless p=NP.

I am talking about decision problem concerned with deciding if the given cycle is shortest possible.

however TSP is not NP-complete , it is P-Hard.

hope you will understand what i am saying.

thank you.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.