I've began studying some CS recently, and I've faced the TSP. The decision problem version of the TSP is NP-complete, right? I've noticed (and elaborated myself) that there exists several polynomial time approximations for the TSP. Combined with the decision problem, this "lowers" the complexity of the algorithm for some values given for the decision, because those values may lie outside of the estimation: say the decision asks for a path no longer than 50 and we find a path of 150 which is at most 2x the minimum path, then we would only need polynomial time for evaluating it.

So my question is as follows: is it possible to assemble algorithms with polynomial time (with any polynomial order) that approximate the TSP to a given ratio? Because then, I could be able to add a series of algorithms before the actual non-polynomial time algorithm to progressively lower it's complexity. Assembling this series of algorithms to find the exact solution would probably require an infinite series of polynomial time, which cannot have polynomial time as a whole. But I think it is possible to use tricks to limit this to a finite number, which would result in a total polynomial time for any given decision value. Think about it: the worst case of this problem is when the decision parameter is exactly the TSP solution - we thus have some information about it. Since P probably differs from NP, I guess there are no such algorithms?

Sorry If I sound a bit confusing, I don't know If my thoughts make much sense mathematically.

  • 2
    $\begingroup$ As you indicate in the question itself, the problem of determining a polynomially long series of approximations that eventually lead to an optimal solution for the TSP is as hard as the TSP itself, since a solution to the former will solve the latter. $\endgroup$ May 6, 2011 at 15:40
  • $\begingroup$ The main point is the dependency of the running time on the approximation parameter $\epsilon$. If $NP \neq P$ then the dependency of the running time on the $\epsilon$ will be bad (e.g. $n^{2^{-\epsilon}}$ is bad), it will be polynomial for each fixed $\epsilon$ but the exponent will grow too quickly w.r.t. $\epsilon$. For any input $x$ one can find an $\epsilon (x)>0$ which will grantee that any $\epsilon$-approximation will be a perfect answer, so one does not need to go to limit. But when this good enough value $\epsilon(x)$ is combined with the algorithm, the result should not be in $P$. $\endgroup$
    – Kaveh
    May 7, 2011 at 4:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.