Is generating all strings permutation NP Complete?

Question

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?

Answer 1

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?