tag:blogger.com,1999:blog-3722233.post2825192225910381396..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: Euclidean TSP is NP-hard but not known to be in NP. Why not known?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-47859008650323265352022-11-14T18:26:12.082-06:002022-11-14T18:26:12.082-06:00When algorithms aren't restricted to compariso...When algorithms aren't restricted to comparisons they can sort in o(n log n) time. One natural model is the word-RAM model where the machine consists of w-bit words, the input is n integers of w bits each, and one can do normal operations like addition, multiplication, shifts, and indirect addressing on w-bit words at unit time per operation.<br /><br />In this model, the best deterministic sorting algorithms are O(n loglog n) time and the best randomized ones take O(n logloglog n) time. (In fact, if w is O(log n) then radix sort will work in linear time and if w is at least log^{2+\Omega(1)} n then a sorting algorithm of Hagerup et al. will also do this in linear time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77967357029130763292022-11-13T13:27:42.367-06:002022-11-13T13:27:42.367-06:00At some point, I was thinking that you can reduce ...At some point, I was thinking that you can reduce "sorting a list of numbers" to a TSP problem. Since if the numbers are just points on the x-axis, presumably the shortest TSP tour goes through them in order. Although it might be increasing or decreasing, and might well start in the middle; so there would be a linear amount of tweaking the tour, to get a sorted list.<br /><br />I was then wondering if the lower bound for sorting, of $\Omega(n \log n)$ comparisons, applied to TSP. Unfortunately, that doesn't really make sense, because I don't think the comparison model isn't really well-defined for TSP. (By which I mean, I can't think of a good way to phrase TSP as "a series of comparisons".)<br />Josh Burdickhttps://www.blogger.com/profile/12231348292069164630noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72552050873886786172022-11-10T19:27:48.641-06:002022-11-10T19:27:48.641-06:00Thanks Eric. Sorry that I misread Kayal and Saha....Thanks Eric. Sorry that I misread Kayal and Saha.Paul Beamehttps://www.cs.washington.edu/people/faculty/beame/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8797799670617243782022-11-09T11:32:07.971-06:002022-11-09T11:32:07.971-06:00The inputs to this problem are integers. Thus the...The inputs to this problem are integers. Thus the problem isn't really that it's hard to get a handle on real numbers. And in fact, it is quite reasonable to conjecture that one can solve the question by computing the bits of each square roots out to a polynomial number of decimal digits, which would put the problem into P. We know that computing an exponential number of decimal digits is sufficient, but we don't know anything better. The problem arises in enough different settings, so that it isn't quite fair to dismiss it as "silly".Eric Allenderhttps://www.blogger.com/profile/07417405562053586552noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61461098744756186492022-11-09T11:07:18.029-06:002022-11-09T11:07:18.029-06:00isn't this question kind of silly though? I me...isn't this question kind of silly though? I mean we can check the inequality to basically any desired level of precision. I guess my question is, is there any real difficulty to the problem outside of that it's hard to get a handle on real numbers in a computational model? Perhaps an equivalent formulation that feels more like a typical computational problemAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-325396000630905822022-11-08T18:47:24.766-06:002022-11-08T18:47:24.766-06:00Although I'm a big fan of the [Kayal, Saha] pa...Although I'm a big fan of the [Kayal, Saha] paper, they do NOT provide a better upper bound on the Sum.of.Square.Roots problem. In the paper of mine (joint with Peter Buergisser, Peter Bro MIltersen, and Johann Kjeldgaard-Pedersen) that Paul mentions, we show that the Sum.of.Square.Roots problem is in PH^PP^PP. I really wish that someone would improve this bound.Eric Allenderhttps://www.blogger.com/profile/07417405562053586552noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23346175018472131832022-11-08T10:39:04.823-06:002022-11-08T10:39:04.823-06:00Allender et al. showed that this problem is in the...Allender et al. showed that this problem is in the counting hierarchy, CH (https://epubs.siam.org/doi/epdf/10.1137/070697926) and I think that Kayal and Saha (https://dl.acm.org/doi/abs/10.1145/2382559.2382560) improve this to (coRP)^PP. I am not sure if there is anything better than their bounds on precision.Paul Beamehttps://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69365782519407370902022-11-08T02:30:05.764-06:002022-11-08T02:30:05.764-06:00I've recently seen results on related problems...I've recently seen results on related problems. For instance, this paper was published at LICS'22: https://arxiv.org/abs/2202.07961. This is about (generalizations of) the decision version of the problem, that is testing whether a sum of square roots equals zero. The generalization is actually to test whether a polynomial vanishes when evaluated on some given radicals (not only square roots).B.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71694761818260726112022-11-07T19:49:39.684-06:002022-11-07T19:49:39.684-06:00It is in ∃ℝ (see https://en.wikipedia.org/wiki/Exi...It is in ∃ℝ (see https://en.wikipedia.org/wiki/Existential_theory_of_the_reals) which implies that it is in PSPACE. It's easy to write an ∃ℝ formula expressing it as the conjunction of r_i^2=a_i, r_i≥0, and sum(r_i)≤k.But ∃ℝ contains NP, whereas https://en.wikipedia.org/wiki/Sum_of_radicals cites a result of Blömer that if the sum of radicals problem is in NP it's also in coNP, suggesting that it is unlikely to be complete for ∃ℝ.David Eppsteinhttps://www.ics.uci.edu/~eppstein/noreply@blogger.com