http://www.cs.cmu.edu/~anupamg/adv-approx/
This material is based upon work supported by the National Science Foundation under Grant No. CCF-0747250. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).
Wednesday, January 16, 2008
Min-R^2-TSP
Did anybody catch why the Min-$\mathbb{R}^2$-TSP problem is not known to be in NP?
Isn't it because there might not be a polynomial time verifier, as the tour length might be an irrational number and the verifier might have to check an infinite number of bits?
Yep, that's right Ali. More specifically, the verifier seems to need to solve the notorious "Sum of Square Roots" problem: Given integers a_1, ..., a_n and b, decide if sum_i sqrt(a_i) <= b.
It seems "obvious" that this should be in P, but when it comes down to brass tacks, the only obvious upper bound is PSPACE.
I think that verification is actually equivalent to square root sum.
Note that sqrt sum with equality is in P (highly non-trivial).
Also sqrt sum is a special case of SDP feasibility. (Recall that for SDP it is easy to find an almost feasible solution, but not an exactly feasible one.)
3 comments:
Isn't it because there might not be a polynomial time verifier, as the tour length might be an irrational number and the verifier might have to check an infinite number of bits?
Yep, that's right Ali. More specifically, the verifier seems to need to solve the notorious "Sum of Square Roots" problem: Given integers a_1, ..., a_n and b, decide if sum_i sqrt(a_i) <= b.
It seems "obvious" that this should be in P, but when it comes down to brass tacks, the only obvious upper bound is PSPACE.
A recent result of Allender, Burgisser, Kjeldgaard-Pedersen, and Miltersen reduces this slightly to P^PP^PP^PP (!!!).
I think that verification is actually equivalent to square root sum.
Note that sqrt sum with equality is in P (highly non-trivial).
Also sqrt sum is a special case of SDP feasibility. (Recall that for SDP it is easy to find an almost feasible solution, but not an exactly feasible one.)
Ilias
Post a Comment