问题标签 [np-complete]

是否可以将任何子图同构问题转换为子集和问题，以便可以使用可用于解决子集和问题的动态规划技术来解决 SGI 问题？

最小硬币找零问题是一个 NP 完全问题，但对于某些硬币集合，贪心算法（首先选择最大面额）有效。给定一组表示硬币值的整数，确定贪心算法是否足够的最快算法是什么？一种明显的方法是将您的动态编程解决方案构建到最大面额，并查看每个解决方案是否比贪婪方式产生更好的解决方案。但是是否有更快的“数学方法”来检测它？

我有这个任务来证明这个问题：

有限字母 £，两个字符串 x,y € £* 和一个正整数 K。有没有办法通过一系列 K 或更少的单个符号删除或相邻符号交换操作从字符串 x 导出字符串 y？

是 np 完全的。我已经知道我必须从集合覆盖问题的决策版本进行转换，但我不知道如何做到这一点。任何帮助，将不胜感激。

很容易看出 n! 增长速度比几乎任何 N 次方都慢（比如 100^N），因此，如果一个问题被认为是 NP 完全的并且发生了一个！近似解决方案的算法，人们会做史努比舞。

我对这种情况有两个问题：

1. 会不会！算法被认为是多项式时间内的解决方案？阶乘当然不是一个提升到幂的术语。
2. 如果找到一个！解决方案意味着我们有一个相当快的算法，因为 n! 增长速度超过 2^N，那么这是否意味着某些 NP 完全问题不需要启发式/逼近算法（晦涩的情况除外）？

当然，这两个问题依赖于第一段的真实性；如果我错了，请告诉我。

我看到了这个XKCD 漫画中提到的问题的 ECLiPSe 解决方案。我试图将其转换为纯 Prolog。

我不认为这是人们能想到的最好/最具声明性的解决方案。有没有人有任何改进的建议？提前致谢！

我遇到了许多可以表述为图形问题的问题。它通常是 NP 难的，但有时可以证明该图是平面的。因此，我对学习这些问题和算法很感兴趣。

据我所知：

1. 平面图中的最大切割
2. 平面图中的四色
3. 三次平面图中的最大独立集

希望有人能完成这份清单。

我研究了很多关于减少的问题，但我有一个很糟糕的问题：我从 CLRS 得到这个：

“ ...通过将解决问题 A 的问题“简化”为解决问题 B，我们用 B 的“容易性”来证明 A 的“容易性”。”

我从“Christos H. Papadimitriou 的计算复杂性”中得到这个：

“……如果 B 简化为 A，问题 A 至少和问题 B 一样难。”

我对这两个概念感到困惑：当我们使用 easyiness 时，我们说问题 X 减少为问题 Y，如果我们有 Y 的多项式时间算法并且减少过程是在多项式时间内完成的，那么问题 X 可以在多项式时间内解决，而 X 是比 Y 容易，或者至少不比 Y 难。

但是当我们使用 hard 时，我们说问题 X 简化为问题 Y，并且 Y 比 X 更容易，或者至少不比 X 更难。

我真的很困惑，请帮助我。特别感谢。

我知道它已被证明是 NP 完全的，这没关系。我目前正在用分支和界限解决它，我将初始上限设置为乘法次数，它将采用正常的二进制平方/乘法算法，它确实给出了正确的答案，但我对运行不满意时间（200 左右的数字可能需要几秒钟）。这是一个 NP 完全问题，我并不期待任何壮观的事情。但通常有一些技巧可以在一定程度上控制实际时间。

在实践中是否有更快的方法来做到这一点？如果是这样，它们是什么？

NP完全的定义是

一个问题是 NP 完全的，如果

1. 它属于NP类
2. NP多项式中的所有其他问题都转换为它

那么，如果 NP 中的所有其他问题都转换为 NP 完全问题，那么这是否也意味着所有 NP 问题也是 NP 完全问题？如果两者相同，那么对它们进行分类有什么意义？

换句话说，如果我们有一个 NP 问题，那么通过（2）这个问题可以转化为一个 NP 完全问题。因此，NP 问题现在是 NP-完全的，并且 NP = NP-完全。两个类是等价的。

只是想为自己澄清一下。

如果我有一个决策问题 A，并希望证明它是 NP 完全的。是否足以证明另一个 NP 完全问题多项式简化为 A，或者我必须证明另一个 NP 完全问题多项式转换为 A？

也就是说，我可以证明

还是我只限于一次使用solve_A，如图所示

我发现一些消息来源说前者，而其他消息来源说后者，这让我有点困惑。