3 ms·
Nitpicking, I know, but I think the author has misinterpreted the XKCD strip. IMO, " - as fast as possible, of course. Want something on the Travelling Salesman
by scubbo 13y ago
Nitpicking, I know, but I think the author has misinterpreted the XKCD strip. IMO, " - as fast as possible, of course. Want something on the Travelling Salesman?" is not a continuation of the client's request (Give me set of appetizers, fulfilling these requirements, as quickly as possible), but rather a response to the waiter ("I have to see to these other tables" - "and you have to do so as quickly as possible"). This makes the mention of "Travelling Salesman" more appropriate (since it deals with optimizing travel time for certain visits).
Am I misinterpreting the dialogue?
(Not that it matters, of course!)
- jasallen 13y agoHuh, I didn't get that, but I think you're right. deep :-)
- grinnbearit 13y agoYou're right, its actually the sum of subsets problem
- raverbashing 13y agoEvery NP problem can be converted in another NP problem, so you could probably try to convert your subset problem to a TSP problem (but it wouldn't be useful in practice)
- a-nikolaev 13y agoNitpicking: In general, an NP problem can be reduced to an NP-hard problem (in poly-time).
- javajosh 13y agoNo, you're not misinterpreting. The character is drawn holding a bunch of papers, and he's apparently offering a paper on Traveling Salesman to be "helpful" to the waiter who has 6 tables to visit "as fast as possible". So, in a way, this entire solution is the product of an error in reproduction. :)