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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Mar 1 '13 at 12:34
  • $\begingroup$ @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.). $\endgroup$ – Stasys Mar 2 '13 at 11:45

Your Answer

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

Browse other questions tagged or ask your own question.