具有 NP 复杂性的最长路径问题示例？
Example of longest path problem having a NP complexity?
我在网上看到找最长路径的问题是NP-Complete问题
出于某种原因，我的老师告诉我这不是 NP 完全问题。
所以现在我正在寻找一个示例，该示例显示获得最长路径所需的计算量大于多项式时间。
目前，我只看到它具有多项式复杂度时间的示例。
谁能给我证明这个问题是 NP 完全的？
对于初学者来说，根据您如何表述最长路径问题，实际上问题可能是 NP-hard 但不是 NP-完成。 NP-此问题的完整版本如下：
Given a graph G and a length k, does G have a simple path of length k or more?
已知此问题是 NP-complete，原因我稍后会详细说明。然而，这个密切相关的问题 not 实际上 NP complete:
Given a graph G, what is the longest simple path in G?
第二个问题 NP-hard 但不是 NP-complete。对于NP-完整的问题，问题必须是决策问题，答案是布尔值"yes"的问题或 "no." 但是，问题的第二个版本不是决策问题，因此它不可能在 NP 中，所以它不可能是 NP-完成。当你说最长路径问题不是 NP-complete 时，你的老师完全有可能在考虑这个问题，尽管我不能肯定地说。
至于最长路径问题为什么是NP-complete，需要争论两点：
这个问题在NP中。直觉上，有一种有效的方法来检查问题的答案是否定的。
这道题 NP-hard。也就是说，有一个 NP-hard 问题可以归结为它。
对于第 (1) 点，直觉是如果问题 "does this graph have a simple path of length 137 or more?" 的答案是 "yes,"，那么可以通过一些简单的方法向某人证明这一点。只要给他们那条简单的路。一旦他们有了路径，他们就很容易检查它是否确实满足要求。 （现在，找到这条路可能真的很难。但是一旦我们以某种方式将它隔离开来，就不难说服人们相信它有效。）
对于第 (2) 点，一般的做法是从现有的 NP-hard 问题开始，并将其简化为我们的问题。在这里，我们将从哈密顿路径问题开始，即：
Given a graph G, is there a simple path that passes through every node in G once and exactly once?
以下是我们如何将该问题简化为最长路径问题。从图 G 开始。现在，问这个问题：G 是否有一条长度至少为 n - 1 的简单路径，其中 n 是 G 中的节点数？如果是这样，那么这条简单路径必须访问每个节点一次且恰好一次，否则路径中没有足够的节点使其长度至少为 n - 1。相反，如果不是，则没有哈密顿路径，因为任何哈密顿路径都符合要求。因此，如果我们能高效地解决最长路径问题，我们就能高效地解决哈密顿路径问题。由于哈密顿路径问题是 NP-hard，因此最长路径问题也是如此。
现在，这个问题是 NP-complete 的事实并不意味着它没有多项式时间解。 P vs NP 的问题还没有解决，不知道是不是P = NP or P ≠ NP 我们不能说最长路径问题是否有多项式时间算法.我们可以说的是，在多项式时间内没有已知算法运行（你提到一些网站声称他们有针对这个问题的多项式时间算法，但事实并非如此听起来不错；如果是这样，那么发现该算法的人将成为百万富翁）。
现在，您可以问一个后续问题：为什么哈密顿路径问题 NP-hard？证明这一点的通常方法是从 3SAT 开始，然后进行基于小工具的巧妙还原。在这里探索的时间太长了，但是大多数入门理论教科书（包括 Sipser 的著名教科书）都很好地解释了这一点。
我在网上看到找最长路径的问题是NP-Complete问题
出于某种原因，我的老师告诉我这不是 NP 完全问题。 所以现在我正在寻找一个示例，该示例显示获得最长路径所需的计算量大于多项式时间。
目前，我只看到它具有多项式复杂度时间的示例。
谁能给我证明这个问题是 NP 完全的？
对于初学者来说，根据您如何表述最长路径问题，实际上问题可能是 NP-hard 但不是 NP-完成。 NP-此问题的完整版本如下：
Given a graph G and a length k, does G have a simple path of length k or more?
已知此问题是 NP-complete，原因我稍后会详细说明。然而，这个密切相关的问题 not 实际上 NP complete:
Given a graph G, what is the longest simple path in G?
第二个问题 NP-hard 但不是 NP-complete。对于NP-完整的问题，问题必须是决策问题，答案是布尔值"yes"的问题或 "no." 但是，问题的第二个版本不是决策问题，因此它不可能在 NP 中，所以它不可能是 NP-完成。当你说最长路径问题不是 NP-complete 时，你的老师完全有可能在考虑这个问题，尽管我不能肯定地说。
至于最长路径问题为什么是NP-complete，需要争论两点：
这个问题在NP中。直觉上，有一种有效的方法来检查问题的答案是否定的。
这道题 NP-hard。也就是说，有一个 NP-hard 问题可以归结为它。
对于第 (1) 点，直觉是如果问题 "does this graph have a simple path of length 137 or more?" 的答案是 "yes,"，那么可以通过一些简单的方法向某人证明这一点。只要给他们那条简单的路。一旦他们有了路径，他们就很容易检查它是否确实满足要求。 （现在，找到这条路可能真的很难。但是一旦我们以某种方式将它隔离开来，就不难说服人们相信它有效。）
对于第 (2) 点，一般的做法是从现有的 NP-hard 问题开始，并将其简化为我们的问题。在这里，我们将从哈密顿路径问题开始，即：
Given a graph G, is there a simple path that passes through every node in G once and exactly once?
以下是我们如何将该问题简化为最长路径问题。从图 G 开始。现在，问这个问题：G 是否有一条长度至少为 n - 1 的简单路径，其中 n 是 G 中的节点数？如果是这样，那么这条简单路径必须访问每个节点一次且恰好一次，否则路径中没有足够的节点使其长度至少为 n - 1。相反，如果不是，则没有哈密顿路径，因为任何哈密顿路径都符合要求。因此，如果我们能高效地解决最长路径问题，我们就能高效地解决哈密顿路径问题。由于哈密顿路径问题是 NP-hard，因此最长路径问题也是如此。
现在，这个问题是 NP-complete 的事实并不意味着它没有多项式时间解。 P vs NP 的问题还没有解决，不知道是不是P = NP or P ≠ NP 我们不能说最长路径问题是否有多项式时间算法.我们可以说的是，在多项式时间内没有已知算法运行（你提到一些网站声称他们有针对这个问题的多项式时间算法，但事实并非如此听起来不错；如果是这样，那么发现该算法的人将成为百万富翁）。
现在，您可以问一个后续问题：为什么哈密顿路径问题 NP-hard？证明这一点的通常方法是从 3SAT 开始，然后进行基于小工具的巧妙还原。在这里探索的时间太长了，但是大多数入门理论教科书（包括 Sipser 的著名教科书）都很好地解释了这一点。