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 cities cities cities.
- 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.