# Clarification of Definition for Functional version of TSP

The decision version of $TSP$ is $NPComplete$. I was reading about the functional version of $TSP$ i.e. the class $FP^{SAT}$.

It is mentioned in the original paper that TSP is complete for the class $FP^{SAT}[n^{O(1)}]$. By definition of the class, it means TSP can be solved in polynomial time by making $[..]$ calls to an $NP$ Oracle.

But I am still confused what $n$ is in case of a TSP instance?

• Generally speaking, $n$ is the input size in bits, though in graph problems $n$ is usually the number of vertices. Assuming this is the unweighted version, it's not important whether $n$ is the number of vertices or the size of the input, since these are polynomially related. – Yuval Filmus Jul 4 '17 at 18:08
• Thank you. This is the paper. sciencedirect.com/science/article/pii/0022000088900396 The Instance is : "Graph with integer weights on the edges". I assume its an undirected graph as they do not talk about directed edges. So, do I take the 'input size' as the number of bits required to represent the incident matrix (with each entry 0 or the weight of the edge) of the problem ? – J.Doe Jul 4 '17 at 18:18
• Right, $n$ is the input size, unless they are doing something in a non-standard way. – Yuval Filmus Jul 4 '17 at 18:26
• @YuvalFilmus, what I thought is that $n$ is number of vertices. Only then binary search for TSP requires linear amount of calls. – rus9384 Jul 4 '17 at 21:10
• @rus9384 The upper bound holds even in the presence of weights – the increase in input size is in your favor. – Yuval Filmus Jul 5 '17 at 2:17

## 1 Answer

In definitions of complexity classes, $n$ is always the input length in bits.

Often the definitions are invariant under polynomial blowup (for example, polytime and logspace), and in such cases you can also take $n$ to be other parameters of the input, the resulting class being the same. For example, if the input is an unweighted graph, you can take $n$ to be the number of vertices.

• I am still trying to grasp the concepts in terms of functional versions as they are very confusing. The paper says Clique is complete for $FP^{SAT}[log(n)}]$. Thus, for Vertex Count (V) - 1024, Input Size (n) = Log(VertexCount^2)) = 20. And the clique could be solved in $FP^{SAT}[log(n)}]$, so the maximum number of calls we are allowed to the NP Oracle are 5. I am not sure how we can solve clique using that many calls in polynomial time? And it gets worse as n doubles. – J.Doe Jul 5 '17 at 5:29
• No – the input size is the length of the input in bits. In this case $O(\log n)$ denotes the same class of functions whether $n$ is the input length or whether $n$ is the number of vertices. Note that $\log n$ in this context probably means $O(\log n)$ – usually big O's are hidden in definitions of complexity classes. – Yuval Filmus Jul 5 '17 at 8:43
• Ok. But, then I can solve the weighted TSP using $O(log n)$ calls to NP Oracle, not $O(n)$! – J.Doe Jul 5 '17 at 9:12