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.

$\endgroup$
  • 1
    $\begingroup$ What is your function, you should add more information. $\endgroup$ – user742 Apr 20 '12 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 '12 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 '12 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 '12 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 '12 at 16:04
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.

$\endgroup$
  • 2
    $\begingroup$ "Is there a tour of cost at most $k$?" is a decision problem. $\endgroup$ – Louis Apr 20 '12 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 '12 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 '12 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 '12 at 19:06
  • 1
    $\begingroup$ (For what it's worth, I think Louis gave a great answer... +1) $\endgroup$ – Patrick87 Apr 20 '12 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$)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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