如何证明一个概率在 NP 中并且它是 NP 完全的
How to show that a prob is in NP and that it is NP-complete
最长路径
我们有一个图 G=(V,E)，对于 E 中的每个 e，Z^(+) 中的长度 l(e)，正整数 K 和 V 中的两个节点 s,t。
问题是 G 中是否存在一条从 s 到 t 的长度至少为 K 的简单路径？
- 证明问题Longest Path属于NP。
- 证明最长路径问题是 NP 完全问题，将哈密顿路径归约到它。
- 证明如果图是有向无环的则问题可以在O(|V|+|E|)时间内解决。
你能给我一个提示，我们如何证明这个问题属于 NP？
另外，我们如何将一个问题归结为另一个问题，以证明后者是 NP 完全的？
编辑:
那么为了说明问题属于NP问题，是不是要画个简单的，统计边的长度之和呢？
我们是不是说下面的例子？
我们看到从节点s到节点t的路径长度等于l((s,w))+l((w,t))=3+12=15，所以有不是 G 中从 s 到 t 的长度至少为 K 的简单路径。
还是满足以下要求？
"Given a a simple path , we can easily check if its length is at least K(by simply computing the sum of lengths of all edges in it). Thus, it is in NP."
编辑 2：您能否进一步解释一下为什么我们通过将所有边的长度设置为 1 并设置 K = 在多项式时间内将哈密顿路径问题减少到这个问题|V| - 1 个？
编辑 3：假设我们有一个问题 A 和一个问题 B，并且已知 B 是 NP 完全问题。如果我们想证明 A 也是 NP-complete，我们是否以这种方式更改 A 的数据，以便我们遇到与问题 B 相同的问题，从而推断出 A 也是 NP-complete？还是我理解错了？
编辑 4：此外，我们如何证明如果图是有向且无环的，那么问题可以在 O(|V|+|E|) 时间内解决？
编辑 5：哈密顿路径的所有边的长度都等于 1，对吗？如果我们有 V 个顶点，那么最长路径的长度是 V-1，是吗？但是在我们的问题中，边的长度不是特定的，K 也不是一个固定的数字。因此，如果我们将所有边的长度设置为 1 并设置 K = |V| - 1，我们不把我们的问题简化为哈密顿路径问题吗？还是我理解错了？
要证明一个问题是NP问题，我们需要证明它可以在多项式时间内得到验证。给定一个证书（在这种情况下是一条简单的路径），我们可以很容易地检查它的长度是否至少为 K（通过简单地计算其中所有边的长度之和）。因此，它是 NP.
Reduction from A to B 的意思是：给定一个A的实例，创建一个B的实例（更准确的说，我们这里感兴趣的是多项式时间缩减）并求解，以便求解原来的问题。那么我们如何在多项式时间内将哈密顿路径问题简化为这个问题呢？这非常简单：我们可以将所有边的长度设置为 1 并设置 K = |V| - 1。然后我们应该尝试图中的所有顶点对 (s, t), s != t 并且如果此问题的解决方案 return 至少一对正确，则 return 正确。否则，我们应该 return false（检查图中是否有一条长度为 |V| - 1 的路径，其中所有边都具有单位长度，这与检查哈密顿路径是否存在其定义完全相同）。
最长路径
我们有一个图 G=(V,E)，对于 E 中的每个 e，Z^(+) 中的长度 l(e)，正整数 K 和 V 中的两个节点 s,t。
问题是 G 中是否存在一条从 s 到 t 的长度至少为 K 的简单路径？
- 证明问题Longest Path属于NP。
- 证明最长路径问题是 NP 完全问题，将哈密顿路径归约到它。
- 证明如果图是有向无环的则问题可以在O(|V|+|E|)时间内解决。
你能给我一个提示，我们如何证明这个问题属于 NP？ 另外，我们如何将一个问题归结为另一个问题，以证明后者是 NP 完全的？
编辑:
那么为了说明问题属于NP问题，是不是要画个简单的，统计边的长度之和呢？
我们是不是说下面的例子？
我们看到从节点s到节点t的路径长度等于l((s,w))+l((w,t))=3+12=15，所以有不是 G 中从 s 到 t 的长度至少为 K 的简单路径。
还是满足以下要求？
"Given a a simple path , we can easily check if its length is at least K(by simply computing the sum of lengths of all edges in it). Thus, it is in NP."
编辑 2：您能否进一步解释一下为什么我们通过将所有边的长度设置为 1 并设置 K = 在多项式时间内将哈密顿路径问题减少到这个问题|V| - 1 个？
编辑 3：假设我们有一个问题 A 和一个问题 B，并且已知 B 是 NP 完全问题。如果我们想证明 A 也是 NP-complete，我们是否以这种方式更改 A 的数据，以便我们遇到与问题 B 相同的问题，从而推断出 A 也是 NP-complete？还是我理解错了？
编辑 4：此外，我们如何证明如果图是有向且无环的，那么问题可以在 O(|V|+|E|) 时间内解决？
编辑 5：哈密顿路径的所有边的长度都等于 1，对吗？如果我们有 V 个顶点，那么最长路径的长度是 V-1，是吗？但是在我们的问题中，边的长度不是特定的，K 也不是一个固定的数字。因此，如果我们将所有边的长度设置为 1 并设置 K = |V| - 1，我们不把我们的问题简化为哈密顿路径问题吗？还是我理解错了？
要证明一个问题是NP问题，我们需要证明它可以在多项式时间内得到验证。给定一个证书（在这种情况下是一条简单的路径），我们可以很容易地检查它的长度是否至少为 K（通过简单地计算其中所有边的长度之和）。因此，它是 NP.
Reduction from A to B 的意思是：给定一个A的实例，创建一个B的实例（更准确的说，我们这里感兴趣的是多项式时间缩减）并求解，以便求解原来的问题。那么我们如何在多项式时间内将哈密顿路径问题简化为这个问题呢？这非常简单：我们可以将所有边的长度设置为 1 并设置
K = |V| - 1。然后我们应该尝试图中的所有顶点对(s, t), s != t并且如果此问题的解决方案 return 至少一对正确，则 return 正确。否则，我们应该 return false（检查图中是否有一条长度为|V| - 1的路径，其中所有边都具有单位长度，这与检查哈密顿路径是否存在其定义完全相同）。