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))?
login/create account
Drupal
CSI of Charles University
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))?