From Allender et al.: square-root sum is in CH

http://ftp.cs.rutgers.edu/pub/allender/slp.pdf

Corollary 1.5 The Sum-of-square-roots problem and the Euclidean Traveling Salesman Problem are in CH.

(CH = Counting hierarchy.)

Do we also know that it is in P^(PP^(PP^PP))?

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options