2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Can you pinpoint which part of the en.wikipedia article you refer to? I found nothing extraordinary, in particular, not the above claim. $\endgroup$
    – greybeard
    Sep 14, 2020 at 6:22
  • $\begingroup$ Under "Euclidean Steiner tree" last sentence: "It is not known whether the Euclidean Steiner tree problem is NP-complete, since membership to the complexity class NP is not known." $\endgroup$
    – Ignirion
    Sep 14, 2020 at 7:45

1 Answer 1

3
$\begingroup$

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} < \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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.