问题标签 [np-hard]

我试图在著名的游戏 Flow 中找到解决问题的方法。http://moh97.us/flow/

谷歌搜索后，我发现这是一个 NP 完全问题。一个好的解决方案是利用启发式和削减。如何轻松发现 NP 完全问题？有时当我阻止时，我看不到明显的解决方案。当NP完全发生这种情况时，最好快速识别它并继续处理下一个问题。

我试图了解 NP-Complete 和 NP-Hard 之间的区别。

下面是我的理解

NP-Hard 问题是不能在多项式时间内解决但可以在多项式时间内验证的问题。
NP-Complete 问题是属于 NP 且也是 NP-Hard 的问题。

上面的定义正确吗？如果是这样，那么问题不是在 NP 中而是在 NP-Hard 中。他们不会比 NP-Complete 问题更难，说他们只能在指数时间内解决和验证吗？

例如，已知集合覆盖决策问题是一个 NP 完全问题。这个问题的输入是一个全域 U、一个 U 的子集族 S 和一个整数 k()。

我感到困惑的一件事是，如果我们让 k=1，那么显然可以通过简单地检查 S 中的每个元素来及时解决问题 |S|。更一般地说，当 k 是常数时，问题可以在 |S| 的多项式时间内求解。这样，只有当 k 也随着 |S| 增加时，时间复杂度才会呈指数级增长，例如 |S|/2、|S|/3...

所以这是我的问题：

1. 我目前的理解是，NP完全问题的时间复杂度测量是根据最坏情况来测量的。谁能告诉我理解是否正确？

2. 我看到有人证明了另一个问题是 NP 难的，他证明输入的集合覆盖决策问题<U,S,|U|/3>可以简化为该问题。我只是想知道为什么他只证明了<U,S,|U|/3>，而不是<U,S,ARBITRARY k>？？这样的证明可靠吗？

非常感谢！

我正在尝试以直观的方式将我听到的 P、NP、NP-Complete 和 NP-Hard 包装起来，这样我就不必记住它们的定义。

在下图中（左侧场景，P != NP），NP-Complete 和 NP-Hard 之间存在重叠区域。这是否意味着某些问题既是 NP-Complete 又是 NP-Hard？根据这个特定的答案，我发现这是矛盾的：NP、NP-Complete 和 NP-Hard 之间有什么区别？.

上面链接中的表格表明 NP-Complete 问题在多项式时间内是可验证的，而 NP-Hard 问题则不是。那么怎么会有重叠呢？

我正在阅读顶点着色算法。我看到解释如何使用 BFS 解决问题的文档（暗示问题可以在 O(|V|+|E|) 中解决。但我也看到它提到这是一个 NP-hard 问题。

这两者如何结合在一起？你能不能给点灯？

这是我遇到的算法，对我来说它看起来像是一般情况下的多项式解决方案：

用数字标识每种颜色。从一个节点开始，并为其分配编号最少的颜色。使用 BFS 访问其每个邻居。在访问一个节点时，检查它的每个邻居的颜色，并分配没有分配给任何邻居的最小编号的颜色。

据说 BFS 方法仅适用于 2 种颜色。我可以看到为什么上述技术不适用于超过 2 种颜色

假设 A、B 和 C 是决策问题。还假设 A 是多项式时间可约化为 B 且 B 是多项式时间可约化为 C。如果 A 和 C 都是 NP-完全的，那么这是否意味着 B 也是 NP-完全的？

我知道，如果 A 是 NP 完全的并且它是多项式时间可简化为 B，那么 B 是 NP 难的。但是，为了使问题成为 NP 完全问题，它必须满足 (1) 它在 NP 中，并且 (2) 它是 NP-hard。

我不知道如何证明 NP-complete 的第一个要求。

这些问题如何落入 P、NP、NP-Hard 等...集合的挂毯中？我不知道是否存在任何此类问题，但引发我思考过程的是考虑旅行商问题的可判定性：

我怀疑我们无法在多项式时间内验证 P 的“最短性”，其中这个决策问题甚至不在 NP 中。那么在这种情况下它落在哪里呢？

近似算法是否与多项式时间近似算法 (PTAS) 相同？例如，可以证明 A(I) <= 2 * OPT(I) 用于顶点覆盖。这是否意味着 Vertex Cover 具有 2多项式时间逼近算法或 PTAS？

谢谢！

注意：斜体字是我发布问题后所做的编辑。

以下施泰纳树有什么区别：（非）度量施泰纳最小树，欧几里得施泰纳最小树，图施泰纳最小树等？其中哪些是 NP 完全的，哪些是 NP 难的？我发现的一些在线资源表明 Steiner 树是 NP 难的，而其他人则认为它是 NP 完全的，但我相信它们指的是问题的不同版本/变体。

更新：没关系，我已经想通了。SMT 的决策问题是 NP 完全的，因为给定 Steiner 树和整数 k，很容易在多项式时间内验证树的成本是否小于或等于 k。但是 SMT 的优化问题没有多项式时间验证器（我们仍然可以找到树的成本，但我们无法验证它是最优解），所以它是 NP-hard。

我遇到了以下问题：

考虑以下启发式： 从仅包含一个顶点的游览开始。在每一步中，找到游览之外的顶点，与游览的某个顶点的距离较小。设 v 为外顶点， u 为内顶点。在游览中添加 v。假设您的边遵循三角形距离属性。我们如何证明这种启发式方法是 TSP 度量问题的 2 近似值？

有谁知道如何开始？

提前致谢