4

Calculating all string permutations of a given string can be solved in O(n!) by trying all possibilities.

Now, looking at the Travel Salesman Problem, we can solve it by trying all permutations of cities. Lets say we have cities A, B and C. Lets say we start at city A. By calculating all permutations of BC string we get ABC ACB, then we just sum (in polynomial time the distance between AB, CB and CA for the first case...)

So isnt this a reduction of the all strings permutation to the travel salesman problem and isnt it a NP Complete problem?

fredcrs
  • 3,558
  • 7
  • 33
  • 55

1 Answers1

5

I think you're confusing some concepts:

What you describe is not "reducing the all permutations problem to TSP", but the opposite: reducing TSP to the all permutations problem. What that proves is that generating all permutations is NP-Hard (at least as hard as the hardest NP problem).

To prove something is NP-Complete, you would also have to prove that it's in NP. But this is not true, right out of the gate: NP is a set of decision problems, and the problem you described isn't a decision problem.

See also: What are the differences between NP, NP-Complete and NP-Hard?

Loonquawl
  • 1,058
  • 1
  • 11
  • 16
  • can np complete and np hard only be solved using exponential solutions? or complexity has nothing to do with complexity class? – fredcrs Jul 27 '17 at 17:08
  • I mean...as far as we know NP Complete and NP Hard can only be solved with exponencial complexity algorithms, right? – fredcrs Jul 27 '17 at 17:15
  • Well, for NP Complete, yes, "as far as we know". More precisely: 1. We know that NP is contained EXPTIME so all problems in it can be solved in exponential time-complexity. 2. Strictly speaking, we don't _know_ that we can't solve all NP problems in better than that, say polynomial time (meaning that we don't have a proof for this). This is the famous P = NP / P ≠ NP problem. But it's widely believed that this is the case. https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP – Loonquawl Jul 27 '17 at 19:27
  • 1
    Oh, and what I said is before is only true for classical algorithms. If you also include quantum algorithms, we know that some problems in NP, (that don't have known classical solutions in P), can be 'solved' in polynomial time with them. https://en.wikipedia.org/wiki/BQP (I put 'solved' in quotes because things are a little fuzzier there, allowing for some error in probabilistic classes) – Loonquawl Jul 27 '17 at 19:41