以下施泰纳树有什么区别：（非）度量施泰纳最小树，欧几里得施泰纳最小树，图施泰纳最小树等？其中哪些是 NP 完全的，哪些是 NP 难的？我发现的一些在线资源表明 Steiner 树是 NP 难的，而其他人则认为它是 NP 完全的，但我相信它们指的是问题的不同版本/变体。
更新：没关系，我已经想通了。SMT 的决策问题是 NP 完全的，因为给定 Steiner 树和整数 k，很容易在多项式时间内验证树的成本是否小于或等于 k。但是 SMT 的优化问题没有多项式时间验证器（我们仍然可以找到树的成本，但我们无法验证它是最优解），所以它是 NP-hard。
我对问题的 NP 完整性和 NP 硬度感到困惑，特别是因为有时看起来它们可以互换使用。
捕获非常简单。NP-complete 是 NP 的一个子类，NP 是多项式时间可验证的决策问题类。因此，只有决策问题可以是 NP 完全的，而优化问题永远不是 NP 完全的。
NP-Hard 意味着任何至少与 NP-complete 一样难的问题，包括决策和优化问题。因此，所有 NP-Complete 决策问题也是 NP-Hard。如果决策问题是 NP-Complete，则优化版本是 NP-Hard，因为如果您有优化的解决方案，您也可以使用它来回答决策问题。然而，反过来不一定是正确的。
因此从技术上讲，根据定义，即使优化问题有多项式时间验证器，它仍然不是 NP 完全的。