问题标签 [np-hard]

我刚刚在维基百科上阅读了 NP 和 P，我有两个问题：

1. 我们可以在多项式时间内求解一个 NP 示例吗？
2. 有没有可以在多项式时间内得到答案的 NP 例子？</li>

我们可以说一个 NP 完全问题是一个既属于 NP 又属于 NP-hard 的问题，但是我们是否可以仅仅因为一个问题是 NP-complete 的事实而完全认为一个问题是 NP-hard 的。

示例：我将一个 NP 完全问题简化a为一个问题b。因此，b现在证明问题是NP完全的。我真的可以说它也是 NP-hard 吗？

给定图的任意两个顶点之间的 m 条最短路径。确定我们是否可以选择 k 条最短路径，使得它们的并集覆盖所有边。

我确信减少必须来自固定的掩护，但我没有办法将其减少到这个问题。请帮帮我

给定一个包含 n 个正整数（n 个偶数）的列表，将该列表分成两个子列表，以使两个子列表中整数之和之间的差异最小化。这是一个 NP 完全问题还是一个 NP 难题？

我刚开始学习复杂性理论。我从过去的四五天开始寻找，只有一件事。是否有任何问题存在于 NP 而不是 NPC 和 NPH。看这个图（认为 P 不等于 NP）。

P外面有空间，不是NPC的一部分。我想知道，是否存在任何问题？

为什么这两个问题，即TSP和哈密顿路径问题都不是 NP 完全的？

它们看起来相同。

没有均匀性限制的超图的顶点着色是 NP 难的吗？我看过一些论文，显示 k-unoform 超图的顶点着色是 NP 难的。但是，我找不到任何明确说明在一般情况下（不仅仅是 k-uniform）超图的顶点着色是否是 NP-hard 的来源。

维基百科：二次规划表示具有线性约束的正定二次规划 (QP) 可以在多项式时间内求解：“对于正定 Q，椭球方法在多项式时间内求解。[6]”

另一方面，混合整数线性规划（MILP）可以转换为二次约束二次规划（QCQP）。我们知道 MILP 是 NP 难的，所以 QCQD 通常必须是 NP 难的（再次来自：维基百科：二次约束二次程序）。

那么这是否意味着如果您的约束中有一个二次项，则问题是 NP 难的，并且如果它是目标函数并且是正定的，那么它可以在多项式时间内解决吗？

查找图的色数是一个 NP-Hard 问题，因此“理论上”没有快速求解器。是否有任何公开可用的软件可以快速计算图形的确切色数？

我正在编写一个 Python 脚本来计算许多图的色数，但即使是小图也需要很长时间。我正在使用的图表范围很广，可以是稀疏的或密集的，但通常少于 10,000 个节点。我将问题表述为一个整数程序并将其传递给 Gurobi 来解决。您对软件、不同的 IP 公式或不同的 Gurobi 设置有什么建议来加快速度吗？

我希望计算精确的色数，尽管如果它们具有合理的理论保证（例如常数因子近似等），我会对计算近似色数的算法感兴趣。

本文解决了块图或二部置换图的最优路径覆盖问题。在其介绍的第三行中，写到最优路径覆盖问题是 NP-Complete 并参考了“Computer and intractability: a guide to the theory of the theory of NP-completeness by David S. Johnson, Michael R. Garey”。但我在书中找不到它的证据。如果有人知道如何证明这个问题的 NP 完备性，那么请分享您的解决方案。

最优路径覆盖问题：
给定一个图 G，找到最小数量的顶点不相交路径，它们一起覆盖图的所有顶点。