Wednesday, January 16, 2008


Did anybody catch why the Min-$\mathbb{R}^2$-TSP problem is not known to be in NP?


Ali Kemal Sinop said...

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?

Ryan O'Donnell said...

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 (!!!).

Anonymous said...

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.)