<p>Non-metric TSP that is TSP and some instance is not hold the triangle inequality is NP-hard by gap-reduction method.</p>

<p>Is this general TSP a complete problem in some functional complexity classes ?</p>

<p>I've read the zoo, but this problem is not mentioned. </p>

CC BY-SA 3.0
2013-03-01T12:34:32.197Z
Are you asking if an optimization problem is complete for a functional complexity class ? I'm not sure why the non-metric aspect comes into play.
Suresh Venkat
CC BY-SA 3.0
2013-03-02T11:45:34.317Z
@Suresh: It seems that metric (as well as Euclidean) aspects only come into play, if we are interested in *approximating* TSP (Christofides, Arora, Mitchel, etc.).
Stasys
<cc.complexity-theory><complexity-classes><optimization>
Nonmetric TSP and Functional Compleixty Classes
shen
# Nonmetric TSP and Functional Compleixty Classes

(Asked by: username_0 on 2013-03-01)

Non-metric TSP that is TSP and some instance is not hold the triangle inequality is NP-hard by gap-reduction method.

Is this general TSP a complete problem in some functional complexity classes ?

I've read the zoo, but this problem is not mentioned.

**Tags:** cc.complexity-theory, complexity-classes, optimization
> **Comments:**
> **username_1**: Are you asking if an optimization problem is complete for a functional complexity class ? I'm not sure why the non-metric aspect comes into play.  
> **username_2**: @Suresh: It seems that metric (as well as Euclidean) aspects only come into play, if we are interested in *approximating* TSP (Christofides, Arora, Mitchel, etc.).  

---

## 0 answers

