斯坦纳最小的树和NP
以下Steiner树之间有什么区别：（非）公制Steiner最小树，欧几里德Steiner最小树，图Steiner最小树等？ 其中哪些是NP完全的，哪些是NP-hard？ 我发现的一些在线资源表明Steiner树是NP难的，其他人则认为它是NP完全的，但我相信他们指的是不同版本/变体的问题。
更新：没关系，我已经想通了。 SMT的决策问题是NP完全的，因为在Steiner树和整数k的情况下，很容易在多项式时间验证树的成本是小于还是等于k。 但是SMT的优化问题没有多项式时间验证器（我们仍然可以找到树的代价，但是我们无法验证它是最优解），所以它是NP难的。
我很困惑NP-completeness和NP-hardness的问题，特别是因为它有时看起来像它们可以互换使用。
捕捉非常简单。 NP-complete是NP的一个子类，它是一类多项式时间可验证的决策问题。 所以只有决策问题可以是NP完全的，并且优化问题永远不会是NP完全的。
NP-Hard意味着任何问题至少与NP完全一样困难，包括决策和优化问题。 因此，所有NP-Complete决策问题也都是NP-Hard。 如果决策问题是NP-Complete，则优化版本是NP-Hard，因为如果您有优化解决方案，您也可以使用它来回答决策问题。 然而，相反并不一定是真的。
因此，根据技术上的定义，即使优化问题具有多项式时间验证器，它仍然不是NP完全的。
链接地址: http://www.djcxy.com/p/40001.html