2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 4 '17 at 18:08
  • $\begingroup$ 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 ? $\endgroup$ – J.Doe Jul 4 '17 at 18:18
  • $\begingroup$ Right, $n$ is the input size, unless they are doing something in a non-standard way. $\endgroup$ – Yuval Filmus Jul 4 '17 at 18:26
  • $\begingroup$ @YuvalFilmus, what I thought is that $n$ is number of vertices. Only then binary search for TSP requires linear amount of calls. $\endgroup$ – rus9384 Jul 4 '17 at 21:10
  • $\begingroup$ @rus9384 The upper bound holds even in the presence of weights – the increase in input size is in your favor. $\endgroup$ – Yuval Filmus Jul 5 '17 at 2:17
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – J.Doe Jul 5 '17 at 5:29
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 5 '17 at 8:43
  • $\begingroup$ Ok. But, then I can solve the weighted TSP using $O(log n)$ calls to NP Oracle, not $O(n)$! $\endgroup$ – J.Doe Jul 5 '17 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.