I was asked to make an algorithm for TSP in determinstic polynomial time.

k = number of cities = found by reading k distances.

- we populate strings t[] of length k on k! tapes containing all instaces of k! 0000,0001 etc by reading string of length n;
- each t[] is replaced by string index; 0214 = cities[0][0] cities[1][2] cities[2][1] cities[3][4].
- replace all t[] with their sum which is equivalent to the distances between the cities.
- find the minimum of t[];
- finding k takes O(k) time.
- making t[] and replacing all t[] with their sum takes O(n) time but O(k!) space;
- finding the minimum of t[] takes O(k!) time;

Therefore the runtime of TSP is (n + k!) since n can be 1 we can change this to k!.

**Edited by fiveworlds, 17 May 2017 - 01:17 PM.**