Why is it hard to show that the euclidean Steiner tree problem is in NP? I read that for the euclidean Steiner tree problem it is known that it is NP-hard, but not known whether it is in NP or not. [Wikipedia]
Shouldn't the euclidean version obviously be in NP since the metric Steiner tree problem is in NP and a non-deterministic TM that decides the metric Steiner tree problem could also decide the Euclidean Steiner tree problem? Or am I missing something that could make the Euclidean version inherently more difficult/different?
I'm guessing the difficulty lies in the fact that euclidean distance is involved, and we don't know if comparing sums of integrer square roots is in NP.
The problem is the following: for integers $a_1, \ldots a_n$ and $b_1, \ldots b_m$, is $\sum\sqrt{a_i} &lt; \sum\sqrt{b_j}$?
This is not known to be in NP and is a major barrier in adapting a lot of computational geometry algorithms from the Real-RAM model to Word-RAM.