# Logic behind a single-tape NTM solving the TSP in \$O({n}^4)\$ time at most I was going through the classic text “Introduction to Automata Theory, Languages, and Computation” by Hofcroft, Ullman, Motwani where I came across a claim that a “single-tape NTM can solving the TSP in $$O({n}^4)$$ time at most” where $$n$$ is the length of the input given to the turing machine (an instance of the TSP). The authors have assumed the encoding scheme as follows:

The TSP’s problem could be couched as: “Given this graph $$G$$ and limit $$W$$ , does $$G$$ have a hamiltonian circuit of weight $$W$$ or less?” Let us consider a possible code for the graphs and weight limits that could be the input. The code has five symbols, $$0$$, $$1$$, the left and right parentheses, and the comma.

1. Assign integers $$1$$ through $$m$$ to the nodes.

2. Begin the code with the value of $$m$$ in binary and the weight limit $$W$$ in binary, separated by a comma.

3. If there is an edge between nodes $$i$$ and $$j$$ with weight $$w$$, place $$(i, j, w)$$ in the code. The integers $$i$$, $$j$$ , and $$w$$ are coded in binary. The order of $$i$$ and $$j$$ within an edge, and the order of the edges within the code are immaterial. Thus, one of the possible codes for the graph of Fig. with limit $$W = 40$$ is

$$100, 101000(1, 10, 1111)(1, 11, 1010)(10, 11, 1100)(10, 100, 10100)(11, 100, 10010)$$

The authors move to the claim as follows:

It appears that all ways to solve the TSP involve trying essentially all cycles and computing their total weight. By being clever, we can eliminate some obviously bad choices. But it seems that no matter what we do, we must examine an exponential number of cycles before we can conclude that there is none with the desired weight limit $$W$$ , or to find one if we are unlucky in the order in which we consider the cycles.

On the other hand, if we had a nondeterministic computer, we could guess a permutation of the nodes, and compute the total weight for the cycle of nodes in that order. If there were a real computer that was nondeterministic, no branch would use more than $$O(n)$$ steps if the input was of length $$n$$. On a multitape $$NTM$$, we can guess a permutation in $$O({n}^2)$$ steps and check its total weight in a similar amount of time. Thus, a single-tape $$NTM$$ can solve the TSP in $$O({n}^4)$$ time at most.

I cannot understand the part of the above paragraph in bold. Let me focus on the points of my problem.

1. What do they mean that the branch would take no more than $$O(n)$$ ?
2. On a multitape $$NTM$$, how can we guess a permutation in $$O({n}^2)$$ steps ?
3. How are we getting the final $$O({n}^4)$$ ?

I neither get the logic nor the computation of the complexity as very little is written in the text. Posted on Categories proxies