1
$\begingroup$

I have a collection $P \subseteq \mathbb{R}^3$ of $N$ particles and there is a function $f : P^2 \to \mathbb{R}$. I want to find which configuration of the system minimizes the value of $f$.

Can this problem (or similar ones) be reduced to TSP? Could you point me to literature on the topic?

In my application, $f$ is the atomic van der waals force, which for each pair of particles of atoms is attractive or repulsive depending on some predefined thresholds.

In addition, it would be great to have a list of concrete examples of problems that can be reduced to TSP.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ What is your function, you should add more information. $\endgroup$
    – user742
    Apr 20, 2012 at 15:50
  • $\begingroup$ I removed the overly broad question about problems reducible to TSP; the main question seems to be about a specific class of problems. However, as it is the question is too vague, as Patrick notes in his answer: votes to close as not constructive. Please add more information, in particular about $f$. $\endgroup$
    – Raphael ♦
    Apr 22, 2012 at 11:28
  • $\begingroup$ the function is the atomic van der waals energy, which for each pair of particles of atoms is attractive or repulsive depending on some predefined thresholds $\endgroup$
    – Open the way
    Apr 22, 2012 at 14:43
  • $\begingroup$ What is a "configuration", and how does $f$ compute a value for it; sum of pairwise energies, maximum pairwise energy, ...? Regarding a list of problems, see Patricks's answer or Garey/Johnson; I doubt such a list will be useful for you, though. $\endgroup$
    – Raphael ♦
    Apr 22, 2012 at 15:46
  • $\begingroup$ A configuration is the specification of 3D coordinates for all particles. The value of the function is the some of pairwise VDW energies. $\endgroup$
    – Open the way
    Apr 22, 2012 at 16:04

2 Answers 2

Reset to default
8
$\begingroup$

Since TSP is NP-complete, most problems you'll encounter in practice can be. (NP is a pretty general class.) A classic paper of Karp gives a large number of other NP-complete problems that, by definition, can be reduced to TSP.

Improve this answer
$\endgroup$
12
  • 2
    $\begingroup$ "Is there a tour of cost at most $k$?" is a decision problem. $\endgroup$
    – Louis
    Apr 20, 2012 at 15:56
  • 3
    $\begingroup$ @SaeedAmiri, the search and decision versions of travelling salesman are polynomial-time reducible to one another, so in the context of this question, the distinction doesn't matter. Problems in P are also in NP of course, so I don't understand the last point you are trying to make. $\endgroup$
    – Aaron
    Apr 20, 2012 at 16:52
  • 3
    $\begingroup$ @SaeedAmiri, the question is "Which search/optimization problems can be reduced to the famous "Travel Salesman Problem"?". The answer is exactly the set of problems in NP. $\endgroup$
    – Aaron
    Apr 20, 2012 at 18:09
  • 2
    $\begingroup$ @SaeedAmiri I don't quite follow your reasoning. Certainly anything in NP can be reduced to either the decision or optimization variant of TSP. So, in that sense, this answer is accurate. What the answer doesn't do is to say which class the OP's problem is in... but that doesn't make the answer wrong, possibly just incomplete. More importantly, it provides a very clear test for whether his problem can be reduced to either TSP: is it in NP? That's a question we can't answer without the objective function; see my answer. $\endgroup$
    – Patrick87
    Apr 20, 2012 at 19:06
  • 1
    $\begingroup$ (For what it's worth, I think Louis gave a great answer... +1) $\endgroup$
    – Patrick87
    Apr 20, 2012 at 19:14
6
$\begingroup$

A decision variant of the problem might be:

Does there exist a configuration of the system such that the objective function assumes a value less than or equal to $y_0$?

It depends entirely upon the form of the objective function. Suppose that the objective function is constant, i.e., $f(x) = c$. Then a constant-time algorithm which solves the decision problem is to return $yes$ iff $c \le y_0$.

Suppose instead that $f(x)$ returns 0 if the Turing machine encoded by $x$ (according to some encoding scheme) halts on itself as input, and 1 otherwise. Then the decision problem is undecidable, since it would allow you to solve the Halting problem; in particular, it is not reducible to TSP.

(Note: in order for the above to create a Halting-Problem scenario, there would need to be some restrictions on the allowed configurations, so that - for instance - only one configuration were possible. This could easily be encoded by the $f$; make all but exactly one configuration result in $f(x) = +\infty$)

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 This is definitely something I didn't cover, and between the two the question seems answered. $\endgroup$
    – Louis
    Apr 20, 2012 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.