# Complexity of an optimisation problem in 3D

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.

– user742
Apr 20, 2012 at 15:50
• 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$.
– Raphael
Apr 22, 2012 at 11:28
• 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 Apr 22, 2012 at 14:43
• 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.
– Raphael
Apr 22, 2012 at 15:46
• A configuration is the specification of 3D coordinates for all particles. The value of the function is the some of pairwise VDW energies. Apr 22, 2012 at 16:04

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.

• "Is there a tour of cost at most $k$?" is a decision problem. Apr 20, 2012 at 15:56
• @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. Apr 20, 2012 at 16:52
• @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. Apr 20, 2012 at 18:09
• @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. Apr 20, 2012 at 19:06
• (For what it's worth, I think Louis gave a great answer... +1) Apr 20, 2012 at 19:14

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$)

• +1 This is definitely something I didn't cover, and between the two the question seems answered. Apr 20, 2012 at 20:48