Space complexity of Travelling Salesman Problem

Question

I am having trouble coming up with the space complexity of the TSP algorithm.

https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

To me the space complexity for the brute force is the cost of storing all possible permutations right ? That should take space O($N!$) where N is the number of cities/nodes/vertexes.

Similarly for the Dynamic Programming algorithm it stores all tours, that is also O($N!$), but the site says the space complexity is O($2^{N}$)

Can someone explain if my logic for space complexities is correct, especially for the Dynamic Programming algorithm.

Thank you

Answer 1

The brute force solution enumerates all permutations. You can easily encode each permutation using $n\log n$ bits, since you can encode it as a list of numbers from $1$ to $n$, and each number takes $\log n$ bits to encode. You can check that a given permutation corresponds to a tour using $O(\log n)$ additional bits of space, so in total the space requirements are $O(n\log n)$.

The dynamic programming solution, as mentioned in the comments, uses a table of size $O^*(2^n)$. This is much more memory than the brute force solution, but the complexity is exponential instead of factorial, which is much better.

(The notation $O^*$ means that we ignore polynomial factors.)

In fact, every problem in NP can be solved using polynomial space, using a brute force approach that simply goes over all possible witnesses, and for each of them, verifying (in polynomial time per witness) whether it is a valid witness. This extends the brute force algorithm for TSP.