Why is it hard to show that the euclidean Steiner tree problem is in NP?
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.