我需要解决一个NP难问题。有希望吗？

Question

有许多实际问题被证明是NP难的。如果我们假设P≠NP，这些问题没有任何多项式时间算法。

如果你必须解决这些问题中的一个，你有希望高效地解决吗？还是你只是运气不好？

Answer 1

如果问题是NP难问题，假设P≠ NP没有这样的算法

• 确定性，
• 始终在所有输入上完全正确，并且
• 对所有可能的输入都有效。

如果你真的需要以上所有的保证，那么你就太倒霉了。然而，如果你愿意解决这个问题，放松一些约束，那么很可能还有希望！这里有几个选项需要考虑。

如果一个问题是NP难的，并且P≠NP，这意味着没有算法能总是有效地在所有输入上产生完全正确的答案。但是如果你不需要确切的答案呢？如果你只需要接近正确的答案呢？在某些情况下，你可以通过使用近似算法来对抗NP难。

例如，NP难问题的一个典型示例是旅行商问题。在这个问题中，您将获得一个表示运输网络的完整图作为输入。图中的每条边都有一个相关的权重。目标是找到一个循环，该循环恰好通过图中的每个节点一次，并且具有最小的总权重。在边权重满足三角形不等式的情况下（即，从点A到点B的最佳路径总是遵循从A到B的直接链接），则可以使用Christofides算法返回一个成本最多为3/2最优的循环。

再举一个例子，0/1背包问题被认为是NP难的。在这个问题中，你有一个包和一组具有不同重量和值的物体。目标是在不超过包重量限制的情况下将物体的最大值装入包中。即使在最坏的情况下计算一个精确的答案需要指数时间，也有可能在多项式时间内将正确答案近似到任意精度。（这样做的算法称为完全多项式时间近似方案或FPTAS）。

不幸的是，我们对某些NP难问题的逼近性确实有一些理论限制。前面提到的Christofides算法给出了TSP的3/2逼近，其中边服从三角形不等式，但有趣的是，它有可能表明，如果P≠NP，则TSP没有多项式时间逼近算法可以在任何最优常数因子内。通常，您需要做一些研究来更多地了解哪些问题可以很好地逼近，哪些问题不能，因为许多NP难问题可以很好地逼近，而许多问题不能。似乎没有一个统一的主题。

在许多NP难问题中，像贪婪算法这样的标准方法并不总是能产生正确的答案，但通常在“合理”的输入上表现得相当好。在许多情况下，用启发式方法来攻击NP难问题是合理的。启发式的确切定义因上下文而异，但通常启发式要么是一种“经常”以有时给出错误答案为代价给出好答案的问题方法，要么是一种有用的经验法则，有助于加快搜索速度，即使它可能并不总是以正确的方式引导搜索。

作为第一种启发式的示例，让我们看看图着色问题。这个NP难问题要求，给定一个图，找到绘制图中节点所需的最小颜色数，以使任何边的endpoint都不具有相同的颜色。事实证明，这是一个特别难用许多其他方法解决的问题（最著名的近似算法有可怕的界限，并且不怀疑有参数化的高效算法）。然而，有许多用于图着色的启发式算法在实践中表现很好。存在许多贪婪着色启发式算法，用于以合理的顺序为节点分配颜色，这些启发式算法在实践中往往表现良好。不幸的是，有时这些启发式算法给出了糟糕的答案，但如果图不是病态构造的，则启发式算法通常工作得很好。

作为第二类启发式的一个例子，看看SAT求解器是有帮助的。SAT，布尔可满足性问题，是第一个被证明是NP难的问题。这个问题要求，给定一个命题公式（通常用联合范式写成），确定是否有一种方法可以给变量赋值，使得整个公式的计算结果为真。现代SAT求解器在许多情况下都非常擅长解决SAT，方法是使用启发式来指导他们对可能的变量分配的搜索。一个著名的SAT求解算法，DPLL，本质上尝试所有可能的分配，看看公式是否可满足，使用启发式来加快搜索速度。例如，如果它发现一个变量总是为真或总是为假，DPLL将在尝试其他变量之前尝试为该变量分配其强制值。DPLL还会找到单位子句（只有一个文字的子句），并在尝试其他变量之前设置这些变量的值。这些启发式的净效果是DPLL在实践中最终非常快，即使已知它具有指数最坏情况行为。

如果P≠ NP，则任何NP难问题都不能在多项式时间内求解。然而，在某些情况下，“多项式时间”的定义不一定符合多项式时间的标准直觉。从形式上讲，多项式时间是指指定输入所需位数的多项式，它并不总是与我们认为的输入同步。

例如，考虑集合划分问题。在这个问题中，你得到了一组数字，需要确定是否有方法将该集拆分为两个较小的集，每个集的总和相同。这个问题的原始解决方案在时间O（2）内运行，只需对所有子集进行蛮力测试。然而，使用动态规划可以在时间O（nN）内解决这个问题，其中n是集合中的元素数，n是集合中的最大值。从技术上讲，运行时O（nN）不是多项式时间，因为数值N仅在log<2

该算法被称为伪多项式时间算法，因为运行时O（nN）“看起来”像多项式，但从技术上讲，输入的大小是指数的。许多NP难问题，特别是涉及数值的问题，都采用伪多项式时间算法，因此在假设数值不太大的情况下很容易求解。

有关伪多项式时间的更多信息，请查看前面关于伪多项式时间的Stack Overflow问题。

如果一个问题是NP难的，并且P≠NP，那么没有确定性算法可以在最坏情况下多项式时间内解决这个问题。但是如果我们允许引入随机性的算法会发生什么呢？如果我们愿意满足于给出一个关于期望的好答案的算法，那么我们通常可以在很短的时间内得到相对好的NP难问题的答案。

举个例子，考虑最大割问题。在这个问题中，你有一个无向图，你想找到一种方法，将图中的节点分成两个非空组A和B，并在组之间运行最大数量的边。这在计算物理学中有一些有趣的应用（不幸的是，我一点也不理解它们，但是你可以仔细阅读这篇论文来了解一些关于这个问题的细节）。这个问题被认为是NP难的，但是有一个简单的随机近似算法。如果你把每个节点完全随机地扔进两组中的一组，你最终得到的割，根据预期，在最优解的50%以内。

回到SAT，许多现代SAT求解器使用一定程度的随机性来引导搜索令人满意的赋值。例如，WalkSAT和GSAT算法的工作原理是选择一个当前不满意的随机子句，并试图通过翻转某个变量的真值来满足它。这通常会引导搜索走向令人满意的赋值，从而使这些算法在实践中运行良好。

事实证明，关于使用随机算法解决NP难问题的能力，有很多开放的理论问题。如果你好奇，可以看看复杂度类BPP及其与NP关系的开放问题。

一些NP难问题需要多个不同的输入。例如，长路径问题以一个图和一个长度k作为输入，然后询问图中是否有一个长度为k的简单路径。子集和问题将一组数字和目标数字k作为输入，然后询问是否存在dds精确到k的数字子集。

有趣的是，在长路径问题的情况下，有一种算法（颜色编码算法），其运行时间为O（（n^{3log n）·bk），其中n是节点数，k是请求路径的长度，b是某个常数。该运行时间在k中是指数的，但在n（节点数）中只是多项式。这意味着，如果k是固定的并且事先已知，则算法的运行时间作为节点数的函数仅为O（n3log n），这是一个很好的多项式。类似地，在子集和问题的情况下，有一个动态规划算法，其运行时间为O（nW），其中n是集合的元素数，W是这些元素的最大权重。如果W预先固定为某个常数，则该算法将在时间O（n）内运行，这意味着可以在线性时间内精确求解子集和。}

这两种算法都是参数化算法的例子。这些算法用于解决NP难问题，将问题的硬度分成两部分——一个是“硬”部分，取决于问题的某个输入参数，另一个是“简单”部分，根据输入的大小优雅地缩放。当所讨论的参数很小时，这些算法可以用来找到NP难问题的精确解决方案。例如，上面提到的颜色编码算法在计算生物学的实践中已经证明非常有用。

然而，有些问题被推测没有任何好的参数化算法。例如，图着色被怀疑没有任何有效的参数化算法。在存在参数化算法的情况下，它们通常非常有效，但是你不能依赖它们来解决所有问题。

有关参数化算法的更多信息，请查看前面的堆栈溢出问题。

指数时间算法不能很好地扩展-对于小到100或200个元素的输入，它们的运行时接近宇宙的生存期。

如果你需要解决一个NP难问题，但你知道输入相当小，比如说，它的大小可能在50到70之间。标准指数时间算法可能不够快，无法解决这些问题。如果你真的需要一个精确的问题解决方案，而这里的其他方法无法解决这个问题，该怎么办？

在某些情况下，对于NP难问题，有“优化”的指数时间算法。这些算法的运行时间是指数的，但没有朴素解决方案那么糟糕。例如，用于3着色问题的简单指数时间算法（给定一个图，确定您是否可以将节点分别用三种颜色之一着色，以便没有边的endpoint是相同的颜色）可能会检查图中节点着色的每一种可能方式，测试它们中是否有任何一种是3着色。有3种可能的方法可以做到这一点，所以在最坏的情况下，对于一些小多项式poly（n），该算法的运行时间将是O（3ⁿ·poly（n））。然而，使用更聪明的技巧和技术，可以开发一种在时间O（1.3289ⁿ）中运行的3-可着色性算法。这仍然是一个指数时间算法，但它是一个更快的指数时间算法。例如，3¹⁹大约是10⁹，所以如果一台html" target="_blank">计算机每秒可以执行10亿次操作，它可以使用我们最初的蛮力算法（粗略地说）在一秒钟内解决多达19个节点的图形中的3-可着色性。使用O（（1.3289ⁿ）-时间指数算法，我们可以在大约一秒钟内解决多达73个节点的实例。这是一个巨大的进步——我们在一秒钟内可以处理的大小增加了三倍以上！

作为另一个著名的例子，考虑旅行推销员问题。TSP有一个明显的O（n！·poly（n））时间解，它通过枚举节点的所有置换并测试这些置换产生的路径来工作。然而，通过使用与颜色编码算法类似的动态规划算法，可以将运行时间提高到“仅”O（n^{22n）。考虑到13！大约是10亿，这个简单的解决方案可以让你在大约一秒钟内求解13个节点图的TSP。相比之下，DP解决方案可以在大约一秒钟内求解28个节点图上的TSP。}

这些快速指数时间算法通常有助于提高实际中可以精确求解的输入的大小。当然，它们仍然在指数时间内运行，因此这些方法对于解决非常大的问题实例通常没有用处。

许多一般来说是NP难的问题都有限制的特殊情况，这些情况已知是可以有效解决的。例如，虽然一般来说，确定一个图是否有k着色是NP难的，但在k=2的特定情况下，这相当于检查一个图是否是二部的，这可以使用修改后的深度优先搜索在线性时间内检查。布尔可满足性一般来说是NP难的，但如果你有一个每个子句最多有两个文字的输入公式，或者公式是由使用XOR而不是包含OR的子句形成的，等等，它可以在多项式时间内解决。在图中找到最大的独立集一般来说是NP难的，但是如果图是二部的，由于柯尼希定理，这可以有效地完成。

因此，如果你发现自己需要解决最初看起来像是NP难问题的问题，首先检查你实际需要解决该问题的输入是否有一些额外的受限结构。如果是这样，你也许能找到一种适用于你的特殊情况的算法，并且在整个通用性上比问题的求解器运行得快得多。

如果你需要解决一个NP难的问题，不要绝望！有很多很好的选择可以让你的棘手问题变得更加平易近人。上述技术中没有一种在所有情况下都有效，但是通过使用这些方法的某种组合，即使面对NP难，通常也有可能取得进展。

希望这有帮助！