gab*_*939 1 theory graph proof longest-path np
我在网上看到，求最长路径问题是NP完全问题。
出于某种原因，我的老师告诉我这不是一个 NP 完全问题。所以现在我正在寻找一个示例，该示例显示获得最长路径所需的计算量大于多项式时间。
目前，我只看到了具有多项式复杂度时间的例子。
任何人都可以给我证明这个问题是NP完全的吗？
对于初学者来说，根据您如何表述最长路径问题，实际上问题可能是NP困难问题，而不是NP完全问题。该问题的NP完全版本如下：
给定图 G 和长度 k，G 是否有长度为 k 或更长的简单路径？
这个问题被称为NP完全问题，原因我稍后会详细介绍。然而，这个密切相关的问题实际上并不是NP完全的：
给定一个图 G，G 中最长的简单路径是什么？
第二个问题是NP难问题，但不是NP完全问题。对于NP完全问题，该问题必须是决策问题，即答案为布尔值“是”或“否”的问题。然而，问题的第二个版本不是决策问题，因此它不能属于NP，因此它不能是NP完全的。你的老师在说最长路径问题不是NP完全问题时完全有可能考虑到这一点，尽管我不能肯定地说。
至于为什么最长路径问题是NP完全问题，我们需要争论两点：
这个问题属于NP问题。直观上，有一种有效的方法来检查问题的答案是否正确。
这个问题是NP难的。也就是说，存在一个NP难问题可以简化为它。
对于第 (1) 点，直觉是如果问题的答案是“这个图是否有长度为 137 或更长的简单路径？” 是“是”，有一些简单的方法可以向某人证明这一点。只需给他们这条简单的路径即可。一旦他们有了路径，他们就可以轻松检查它是否确实满足要求。（现在，找到这条路可能真的很困难。但是一旦我们以某种方式隔离了它，就不难让人们相信它是有效的。）
对于第 (2) 点，一般方法是从现有的NP难问题开始，并将其简化为我们的问题。在这里，我们将从哈密顿路径问题开始，如下所示：
给定一个图 G，是否存在一条简单路径可以通过 G 中的每个节点一次且恰好一次？
以下是我们如何将该问题简化为最长路径问题。从图 G 开始。现在，问一个问题：G 是否有一条长度至少为 n - 1 的简单路径，其中 n 是 G 中的节点数？如果是这样，那么该简单路径必须访问每个节点一次且恰好一次，否则路径中没有足够的节点使其长度至少为 n - 1。相反，如果不是，则不存在哈密顿路径，因为任何哈密顿路径都符合要求。因此，如果我们能够有效地解决最长路径问题，我们就能有效地解决哈密顿路径问题。由于哈密顿路径问题是NP难问题，因此最长路径问题也是 NP 难问题。
现在，这个问题是NP完全问题的事实并不意味着它没有多项式时间解决方案。P与NP问题仍然没有解决，并且在不知道P = NP还是P ≠ NP 的情况下，我们不能说最长路径问题是否存在多项式时间算法。我们可以说的是，没有已知的算法可以在多项式时间内运行（你提到一些网站声称他们有针对这个问题的多项式时间算法，但这听起来不对；如果是这样，无论谁发现该算法都会成为百万富翁）。
现在，您可以问一个后续问题：为什么哈密顿路径问题是NP难问题？证明这一点的通常方法是从 3SAT 开始，并进行基于小工具的巧妙还原。这里要探讨的内容太长了，但大多数入门理论教科书（包括 Sipser 著名的教科书）都很好地解释了这一点。