问题标签 [np]

例如，我知道语言

CFL 的泵引理不是上下文无关的，但我如何证明它属于 NP 而不是 exp。时间、可判定的语言还是可识别的图灵？

编辑：做了一些挖掘，我做的一个疏忽是 NP 中的问题是那些可以通过非确定性图灵机在多项式时间内验证的问题。我怎么知道：a：在多项式时间内存在该语言的验证器，并且 b：NDTM 可以识别它

这是对我之前的问题（关于一个旧的顶级编码器之谜）的跟进。

给定一串数字，找到该字符串等于某个目标数字所需的最小加法数。每次添加都相当于在数字字符串的某处插入一个加号。插入所有加号后，照常计算总和。

例如，考虑“303”和目标总和为 6。最佳策略是“3+03”。

我猜（虽然没有证明）问题是NP完全的。你怎么看？你如何将一个众所周知的 NP 完全问题简化为这个问题？

我真的很困惑为什么 2-CNF SAT 在 P 中，而 3-CNF SAT 在 NPC 中。我读过 CLRS，我了解他们如何证明 3-CNF SAT 在 NPC 中。我不能使用从 SAT 到 2-CNF-SAT 的相同可还原性来证明 2-CNF-SAT 在 NPC 中。我不明白为什么 2-CNF SAT 在 P 中。

我有几个数字数组（数组的每个元素只能取0或1的值）像这样

我希望找到这样的子集，以便在对数组求和时，生成的数组具有单个元素，这些元素是 2 的倍数。例如，v1+v2+v3 给出的结果数组为 2、2、0、2、2。结果数组可以具有任何 2 的倍数的值。

另一个例子：

在此示例中，v1+v2+v5 和 v3+v6+v7 是合适的答案。

我有一个蛮力解决方案，但我想检查是否有更有效的方法。这相当于子集和问题吗？

除了在所有可能的独立集合中找到最大值的蛮力方法之外，我不相信存在一种算法可以在二分图中找到最大独立顶点集。

我想知道找到所有可能的顶点集的伪代码。

假设给定一个具有 4 个蓝色顶点和 4 个红色顶点的二分图。目前我会

我知道这种方式根本不会给我所有可能的独立集组合，因为在第一步之后，我选择了所有不匹配的下一个颜色顶点，而不是逐步完成所有可能。

例如给定一个匹配的图

有没有办法改进这个算法以更好地搜索所有可能性。我知道|二部图的最大集| = |红色| + |蓝色| - |最大匹配|。

问题出现的可能性是，在第一次选择所有可能的红色以获得给定的蓝色时，如果这些红色连接到所有其他可能的蓝色，那么我的集合只有所有 1 个蓝色和其余红色。

我刚刚阅读了有关在多项式时间内将设置分区解决为一半的可能性。但我找不到算法来做到这一点。

我有两个问题：

1. 我在哪里可以得到那个算法？
2. NP问题怎么可能在多项式时间内解决？

如果我想证明一个问题是 np-hard 问题，可以多次使用现有的 np-hard 问题吗？例如在图中使用哈密顿循环 n 次，其中 n 是顶点数？或者我是否需要将图形转换为可以通过使用 1 次的现有 np-hard 问题轻松解决的东西？

和子集问题指出：

给定一组整数，是否存在总和为零的非空子集？

这个问题通常是NP完全的。我很好奇这种轻微变体的复杂性是否已知：

给定一组整数，是否存在k总和为零的大小子集？

例如，如果k = 1，您可以进行二分搜索以在 中找到答案O(log n)。如果k = 2，那么您可以将其归结为O(n log n)（例如，请参阅从总和等于给定数字的数组中查找一对元素）。如果k = 3，那么您可以这样做O(n^2)（例如，请参阅在数组中查找三个元素，其总和最接近给定数字）。

是否有一个已知的界限可以作为这个问题的函数k？

作为动机，我在考虑这个问题如何将数组分成两部分，使两部分的平均值相等？并试图确定它是否实际上是 NP 完全的。答案在于是否存在上述公式。

除非有一个通用的解决方案，否则我很想知道k=4.

与确定性多项式解决方案相比，非确定性多项式解决方案总是不可取的，这是真的吗？请给出适当的推理。

有界因子。

给定数 n，判断它是否有任何小于 k 的适当因数。

这是一个co-Np问题吗？