问题标签 [np]

我想澄清一个概念。为了证明一个问题是 NP 完全的，我们使用约简。

现在假设我有 L<=L'。减少是从 L 到 L' 还是我也可以反过来做？即我可以证明如果 L 可以使用 L' 来解决，那么 L' 是 NP 完全的吗？

我对此感到很困惑。

例如。为了从火腿循环减少到火腿路径，我们采用了倒退的方式。

此外，我无法通过减少火腿循环来解决我必须证明“在至少有 k 个边的图中是否存在从 s 到 t 的路径”的问题。

请给我一个澄清并指导我解决上述问题。谢谢

一般来说，假设我们有一个NPC问题。给它增加更多的约束（让它更困难），这个问题有可能变成 NPH 吗？我知道 NPC 和 NPH 之间的区别，但我不知道如何证明向现有 NPC 问题添加新约束会使其成为 NPH 还是仍然是 NPC？

我正在学习如何证明某事是NP。在 Thomas Cormen 的算法介绍书中，他指出，如果给出某个问题的解决方案，则某些东西是 NP，您可以在多项式时间内验证它是否正确。

假设问题是 2x + 9 = 55，假设我不知道找到正确的 x 值需要多长时间，但是解决问题的算法返回了解决方案 23。然后证明它是 NP，我只需将 23 代入等式，看看这是否需要多项式时间并给我 55？谢谢。

我见过几个调度问题，说这个问题是 NP 困难的。我的问题是 1）当我们说一个问题是 NP 困难时，这是否意味着它不在 NP 中？因为如果它是 NP，我们说这个问题是 NP 完全的。我知道问题出在 NPC 中，如果 a）在 NP 中 b）在 NP 中很难。

应该有一个初始问题来开始构建 NPC 问题集。只有这样，问题才能从集合 NP 添加到集合 NPC 中，表明 NP 中的问题可简化为 NPC 中的第一个问题。那么，第一个添加到NPC的问题是什么，以及如何有人断定它确实是NPC。

（注意：谷歌搜索，没有答案。我希望这里有人的教授在课堂上提到过这样的事情）

我正在寻找 NP 和 NP 完全问题之间的区别。我在 Jason 的 StackOverflow 中找到了这个很棒的答案。关于 NP 完全问题，他说

一个 NP 问题 X，它可以在多项式时间内将任何其他 NP 问题 Y 简化为 X。直观地说，这意味着如果我们知道如何快速求解 X，我们就可以快速求解 Y。准确地说，如果存在多项式时间算法 f 将 X 的实例 x 在多项式时间内转换为 Y 的实例 y = f(x)，则 Y 可简化为 X，并且当且仅当答案f(x) 是肯定的。

我的问题是：哪一个是 NP 完全问题，X 还是 Y？

我很困惑，这是我阅读后的想法：

P 在 NP 中，而 NP 在 NP-Complete 中。因此，所有 P 都可能是 NP 和 NP-Complete？

这是否意味着存在可能是 NP 和 NP-Complete 的排序算法？

希望这听起来不会太愚蠢。

我有两个数组，每个数组都由一对两个整数（int1，int2）组成。我只想计算每个数组对的第一个值的总和，并且我想对第二个值应用乘法（例如）。显然，如果我写这段代码：

tab3 的结果将是 tab3=array([[1, 9],[2, 9],[0, 8]])

这笔款项也适用于第二部分。但我想获得 (1+0),(1+1),(0+0)，因此：tab3=array([1,2,0])

是否可以在不对数组执行循环的情况下获得此结果？

对于一个 NP 完全问题，它必须属于 NP 类，并且必须有一个多项式时间算法将其简化为一个 NP 完全问题。

现在，如果我们只有一个指数时间算法来减少。这个问题还会被称为 NP-complete 吗？还是不存在这样的问题？

编辑：另外请告诉我是否存在任何此类问题，如果存在，那么它属于哪个类？

对于有资格获得 NP 类的问题：

1. 该问题的解决方案必须具有多项式输出长度，并且
2. 解决方案必须在多项式时间内是可验证的。

多项式输出长度的意义是什么？

PS：我认为多项式输出长度是输出在多项式时间内可验证的必要先决条件。（但是仅仅说可以在多项式时间内验证解决方案仍然是足够的。）