1

我在网上看到找到最长路径问题是NP-Complete问题。

出于某种原因，我的老师告诉我这不是一个 NP 完全问题。因此，现在我正在寻找一个示例，该示例显示获得最长路径所需的计算量大于多项式时间。

目前，我只看到了具有多项式复杂时间的示例。

任何人都可以给我证明这个问题是NP完全的吗？

4

1 回答 1

3

对于初学者，根据您如何表述最长路径问题，实际上可能是问题是NP难但不是NP 完全的。这个问题的NP完整版本如下：

给定图 G 和长度 k，G 是否有长度为 k 或更长的简单路径？

众所周知，这个问题是NP 完全的，原因我稍后会详细说明。然而，这个密切相关的问题实际上并不是NP完备的：

给定一个图 G，G 中最长的简单路径是什么？

第二个问题是NP -hard 但不是NP -complete。对于一个NP 完全的问题，该问题必须是一个决策问题，一个答案是布尔“是”或“否”的问题。然而，这个问题的第二个版本不是决策问题，因此它不能在NP中，因此它不能是NP 完全的。您的老师完全有可能在说最长路径问题不是NP 完全问题时正在考虑这一点，尽管我不能肯定地说。

至于为什么最长路径问题是NP 完全的，我们需要论证两点：

  1. 这个问题在NP中。直观地说，有一种有效的方法可以检查问题的“是”答案。

  2. 这个问题是NP难的。也就是说，有一个NP难题可以简化为它。

对于第 (1) 点，直觉是，如果问题的答案是“此图是否有一条长度为 137 或更长的简单路径？” 是“是的”，有一些简单的方法可以向某人展示这一点。只要给他们那个简单的路径。一旦他们有了路径，他们就很容易检查它是否确实符合要求。（现在，找到那条路可能真的很难。但是一旦我们以某种方式将它隔离出来，让人们相信它是可行的并不难。）

对于第 (2) 点，执行此操作的一般方法是从现有的NP难题开始，然后将其简化为我们的问题。在这里，我们将从哈密顿路径问题开始，如下所示：

给定一个图 G，是否有一条简单的路径通过 G 中的每个节点一次且恰好一次？

以下是我们如何将该问题简化为最长路径问题。从图 G 开始。现在，问一个问题：G 是否有一条长度至少为 n - 1 的简单路径，其中 n 是 G 中的节点数？如果是这样，那么该简单路径必须访问每个节点一次且恰好一次，因为否则路径中没有足够的节点使其长度至少为 n - 1。相反，如果不是，则没有哈密顿路径，因为任何哈密顿路径都符合要求。因此，如果我们能有效地解决最长路径问题，我们就可以有效地解决哈密顿路径问题。由于哈密顿路径问题是NP难的，因此最长路径问题也是如此。

现在，这个问题是NP完全的这一事实并不意味着它没有多项式时间解决方案。P与NP问题仍未解决，在不知道P = NP或P ≠ NP的情况下，我们不能说最长路径问题是否存在多项式时间算法。我们可以说的是，没有已知的算法可以在多项式时间内运行（您提到一些网站声称他们有针对这个问题的多项式时间算法，但这听起来不对；如果是这样，那么发现该算法的人将成为百万富翁）。

现在，您可以提出一个后续问题：为什么哈密顿路径问题是NP难的？证明这一点的常用方法是从 3SAT 开始，然后进行巧妙的、基于小工具的归约。在这里探索的时间太长了，但是大多数介绍性理论教科书（包括 Sipser 的著名教科书）都很好地解释了这一点。

于 2018-12-24T02:09:49.707 回答