Travelling Salesman

[fiveworlds]

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

 

 

 

input = list of cities and their distances of length n.

Each city is seperated by a space e.g.

"distance,distance,distance distance,distance,distance distance,distance,distance"
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!.

So TSP is reducible to finding the minimum of a list of numbers. We can find the minimum of 2 numbers with combinatorial logic and by extension we can find the minimum value of k! numbers with combinatorial logic in O(1) time. Therefore TSP is reducible to O(1) time in deterministic polynomial time.

On modern computers we are limited by the von neumann bottleneck etc so the best runtime on a normal computer would be k! since we can only do one if( a < b) at a time if we could do it if(a < b < c) then it would half the runtime.

Edited May 17, 2017 by fiveworlds

[Strange]

Therefore TSP is reducible to O(1) time in deterministic polynomial time.

 

 

Is that second "time" supposed to be space or something? Otherwise the sentence doesn't seem to make much sense.

[fiveworlds]

Is that second "time" supposed to be space or something?

 

 

It'll take O(1) space too since if we make a circuit to solve it we can't go about changing it at runtime.

 

Also my argument has always been that non-determinism doesn't provide any speed increase to solving any of the problems. The real definition for non-determinism can be found in the paper where it was originally defined http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf

 

Also we can show that it isn't in np because it is not easy to verify as if I said a number was the minimum you would still need to do k! checks to prove it was the minimum. Similarly for boolean sat you couldn't say oh this is false because if a = 0 and b =0 then it is false because a = 1 and b =1 might be true.

Edited May 17, 2017 by fiveworlds

[Strange]

So there are no NP problems? Wow.

[fiveworlds]

So there are no NP problems? Wow.

 

 

I dunno where you are getting that from if you refer to the paper where non-determinism is defined the guy who created NDTM mentioned that all nondeterministic turing machines can be simulated by more complicated deterministic turing machines. So all NP problems have to run on non-deterministic turing machines. They aren't sure if we can make deterministic machines run as fast as non-deterministic machines but I am fairly certain that we can. Consider that NDTM can move either left or right. We know from work on colossus that just moving one direction is fastest. Also the other property of a non-deterministic turing machine is the ability to replace a string with any of an array of strings. We can define a DTM that does the same thing with multiple tapes. So to give an example of a DTM using mutiple tape copy operation.

var a = ['a','b','c']
for(i = 0; i < a.length; i = i + 1) {

}

We have 2 tapes there 1 to store the index and 1 to store the array. When using a non-deterministic idea the array is hard coded and not in memory. The only time it is ever really used now is in read only memory for the bios. The paper was written around the time that ROM was invented. EPROM is deterministic. If we have an instruction say a replace with b we can now do what they couldn't do 50 years ago and change b to c.

 

Now we get wikipedia's definition

 

 

Equivalently, the formal definition of NP is the set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine.

 

 

There's basically no difference between the a non-deterministic turing machine and a deterministic turing machine anymore. Once you have the actual definition all the wiki's are just weird and confusing and claymath's paper is just as bad. You'd need to just take a red pen and mark out every single mistake they made and there is so many.

Edited May 17, 2017 by fiveworlds