Talk:Traveling purchaser problem
Add topicLatest comment: 10 years ago by Uziel302 in topic Travelling
 | This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
| ||||||||||||||||||
Our explanation of NP-hardness seems flawed
[edit]The article currently says this:
The problem can be reduced to the traveling salesman problem if each article is available at one market only and each market sells only one item. Thus it is NP-hard.
I don't follow this statement. It seems backward: you don't prove that problem A is NP-Hard by reducing it to some known NP-hard problem B; you prove it by reducing B to A. The cited article is no help, because it simply makes this exact same statement. Can someone clarify? --Doradus (talk) 01:59, 12 May 2014 (UTC)
- Upon reflection, I don't think the original source meant that the algorithm "reduces" in the strict sense of algorithmic complexity; I think they meant it in the sense that the Traveling Purchaser Problem (TPP) is more sophisticated than the TSP, and so if some of the TPP's sophistication is removed, it becomes equivalent to the TSP. --Doradus (talk) 19:50, 19 May 2014 (UTC)
Travelling
[edit]It sould be travelling with two Ls, as in Travelling salesman problem. Uziel302 (talk) 21:38, 13 November 2015 (UTC)