次のシュタイナー木の違いは何ですか: (非) メトリック シュタイナー最小木、ユークリッド シュタイナー最小木、グラフ シュタイナー最小木など? これらのうちどれが NP 完全で、どれが NP 困難ですか? 私が見つけたオンライン リソースの中には、シュタイナー木が NP 困難であることを示唆するものもあれば、NP 完全であることを示唆するものもありますが、それらは問題のさまざまなバージョン/バリアントを参照していると思います。
更新：気にしないでください、私はそれを理解しました。SMT の決定問題は、シュタイナー木と整数 k が与えられた場合、木のコストが k 以下かどうかを多項式時間で簡単に検証できるため、NP 完全です。しかし、SMT の最適化問題には多項式時間検証器がありません (ツリーのコストを見つけることはできますが、それが最適解であることを検証することはできません)。そのため、NP 困難です。