问题标签 [np-hard]

我对不可判定问题和 NP 难题之间的关系有点困惑。NP难问题是不可判定问题的子集，还是它们只是相同且相等，还是它们不可比较？

对我来说，我一直在和我的朋友争论，不可判定的问题是 NP 难题的超集。会存在一些在 NP 中不难但无法确定的问题。但是我发现这个论点很弱并且有点困惑。是否存在不可判定的 NP 完全问题。NP难有什么问题是可判定的吗？？

一些讨论会有很大帮助！谢谢！

对不起这个复杂的名字 - 这是当之无愧的。让我提出问题。

上下文：我有一种定位网络，我想用它做一些分区。

问题定义：我有一个无向加权图 G = {V,E,w}，其中包含一组顶点 V、边 E 和边权重 W。边存在于 V 中的所有顶点之间。

现在，我有大小为 |C1|...|CN| 的循环 C = {C1...CN} st |C1|...|CN| 的总和 等于顶点总数|V|。一个循环 Ci 的得分是路径中所有边的权重之和。

最后，这是目标：我想以这样一种方式拟合 G 中 C 的所有循环，即它们的组合分数在 C 中没有循环相互交叉的约束条件下是最大的。

所以用外行的话来说：我想用定义长度 st 的循环填充一个图形，全局权重是最优的。

我对这个问题的看法：这个问题至少是 NP 难的，因为它可以简化为诸如打包问题或哈密顿循环之类的问题。

最优解甚至可能不是伪多项式。我已经尝试以几种不同的方式（图表）来制定问题，它总是会导致状态爆炸，因此可能无法采用易于处理的 2D 动态编程方法（如果我错了，请纠正我）。

所以看来我可能不得不使用近似方法。想到的一件事是尝试使用其自己的近似方法找到整个图的哈密顿路径。然后下一步是找到“切割”局部最优哈密顿路径以产生循环的位置。有|C|!*|V| 安排这些“切割点”的方法。阶乘来自这些循环的排序和 |V| 的排列。来自起始位置的总数。即使有修剪（即有相同大小的循环），这对于大的|C| 仍然是难以处理的。我想说蛮力对于小的 |C| 是可以的，而对于较大的 |C| 则需要爬山方法来获得局部最优排列的近似值。

无论如何，你们怎么看？

我的问题类似于这里的问题https://cs.stackexchange.com/questions/2244/need-a-np-complete-proof-on-an-example，但有点不同。

这是我的问题：

有A、B、C三个岛，还有很多扇形的木筏。我们必须从 A-->B-->C 建造一座桥，并且每个部分所需的筏板数量是已知的，例如，连接 AB 需要四个筏板，连接 BC 需要三个筏板。

这些木筏原本在不同的位置，它们可以免费旋转。有趣的是，如果需要，它们可以相互重叠。移动一个筏板的距离可以计算为质心原始位置与其展开位置之间的距离。

目标是找到具有移动筏的最小总距离的解决方案，以使桥梁 A-->B-->C 并使用桥梁每个部分的确切筏数。

我习惯用下图来说明我的问题。

从这个图中我们可以看出，排列可能不是一条直线，木筏可以与另一个木筏重叠。

这些筏子的候选位置太多了。看来问题是NPC。我不知道我是否正确以及如何证明它是NPC。有谁知道如何解决它？谢谢！

if l1 is in NP-HARD, 所以对于每个 L2!=empty 集, l1*l2 is in np-hard.

什么时候：

这是真的还是假的，为什么？

我不能批准它，但我也找不到反例。

我正在寻找一个简单的证据来证明Bounded-PCP问题属于 NP-Complete，正如许多教科书所说的那样。我很清楚这个问题是可判定的，但我找不到从 NP-Hard 问题到这个问题的任何减少。

此外，验证算法可能会经过一系列 N 个索引，与 logN 的输入大小 (N) 相比，这些索引是指数级的，那么这个问题怎么会出现在 NP 中呢？

谢谢。

想象一下我有一组字符串，例如：

我想找到可用于构建初始字符串的子字符串的最佳“词典”。标准是存储词典和使用该词典的字符串所需的最小内存量。

例如，对于给定的字符串集，子字符串的最佳词典可能是：

使用以下方式编码的初始字符串集（每个\N表示对词典中字符串 N 的引用）：

用于构建字符串的总共 8 个引用 + 存储词典所需的 14 个字符，而原始字符串中的 22 个字符 + 包含原始字母表的 8 个字符。如果您需要一个精确的足迹公式，假设sizeof( reference ) == sizeof( char )，并且单个字符串（编码和词典中）的足迹是length of string * sizeof( char or reference )，没有额外的开销。

解决这个问题的最佳算法是什么？这个算法有固定的名字吗？NP难吗？如果是这样，是否存在次优但多项式的解决方案？

编辑：我能想出的最佳解决方案如下：在初始字符串集中找到最长的公共子字符串。让该子字符串的分数为 ，说明(substring_length - 1) * total_occurrences_of_it_in_the_set - substring_length该替换保存的字符/引用的数量。现在找到所有较小的子字符串（直到长度为 2）并以相同的方式计算它们的分数。在以这种方式找到的所有子字符串中，得分最高的子字符串获胜并进入词典。然后子字符串在初始字符串集中被对它的引用替换，并且该过程重复，直到我们的字符串集仅包含单个字符和词典引用。之后，将所有剩余的单个字符引入词典，并用它们在集合中的引用替换它们。打分的解释如下：我们去掉substring_length每次出现的字符，添加一个引用（因此-1），并且需要substring_length字符来存储子字符串（因此-substring_length）。

你能想到什么更好的方法吗？

我似乎无法真正理解说问题是 NP-Complete 的真正含义。谁能帮我解决以下问题？

NP完全问题是可以证明不存在在多项式时间内解决它的算法的问题。陈述是真的吗？

我想说这个说法是不正确的，因为任何人都可以真正证明对于任何 NP-Complete 问题都不存在这样的算法吗？通过环顾各种来源，我了解到对于任何 NP-Complete 问题都没有多项式时间算法；但是，无法证明。

任何帮助将不胜感激。谢谢。

我在SO的答案之一中阅读了以下内容：

旅行商问题，正如通常所提出的，是找到连接所有城市的最便宜的路线。这不是决策问题，我们无法直接验证任何提议的解决方案。我们可以将其重述为一个决策问题：给定成本 C，有没有比 C 更便宜的路线？这个问题是 NP 完全的，只需一点点工作，我们就可以像修改后的 NP 完全形式一样简单地求解原始 TSP。因此，TSP 是 NP 难的，因为它至少与 NP 完全问题一样难。

我知道 TSP 是 NP-Complete 但问题是如何 NP-Hard ？我读到NP中但不在P中的问题是NP-Hard。我无法将这件事与 TSP 联系起来。请解释一下。

我使用 BinPack 问题的特殊变体。我使用一种简单的算法 atm，所以我想知道如何调用它来进行一些初步研究。或者有谁知道如何将这个问题减少到已知的问题？

问题：有特定数量和大小的项目 I 和箱 B。

所有 item-size 的总和至少是所有 bin 的总和的大小。

每个箱子都必须装满物品或物品的一部分，以便完全装满。s(b,i)是在 b 中的 i 部分的大小，如果不是，则为 0。

目标是最小化填充所有箱子所需的项目零件数量。

You are given three things

1) An array of 'n' positive and negative integers. 2) A number 'x'. 3) Operators : '+', '-', '%', '/'

Form an expression with the array such that when you evaluate it, the result becomes 'x'.

For example, consider the array [5,3,-1,6,2,3] and x=2, one possible solution would be

5 / 3 + (-1) + 6 / 2 - 1

Assume the result of 5 / 3 is 1(Always the integer division).

I have one more complex variant of this.

In the complex variant of this problem, assume that BODMASS rule don't apply. So, at any point of time you traversed through elements 'm' and you have the intermediate result 'y'. You can apply any of the operators to the 'y' and a[m + 1].

For example, in the variant 1,

5 + 3 - 2 / 2 = 7 ( 2 / 2 evaluated first, so 5 + 3 - 1)

in the variant 2,

5 + 3 - 2 / 2 = 3 (5 + 3 = 8. The array reduced to 8 - 2 / 2. Now, 8 -2 = 6. And array reduced to 6 / 2 which evaluate to 3).

Algo/Math/DS experts?

Is this a NP hard?