如何证明prob在NP中，并且是NP-complete [英] How to show that a prob is in NP and that it is NP-complete

问题描述

我们有一个图G =（V，E），长度l（e）在Z ^（+）中，对于E中的每个e，一个正整数K和两个节点s，t在V中。问题是如果在G中有一条简单的路径，从s到t长度至少为K？

• 显示问题最长路径属于NP。问题最长路径是NP完全的，减少哈密尔顿路径。 显示如果图是有向和无环的，那么问题可以在时间O（| V | + | E。）。

你能否给我提示我们如何证明问题属于NP？
另外，为了表明后者是NP完全的，我们如何才能将问题减少到另一个问题？

编辑：

所以为了证明问题属于NP，我们是否必须绘制一个简单的并计算边长度的总和？

我们举例说以下几点：

我们看到从节点s到节点t的路径长度等于l （（s，w））+ l（（w，t））= 3 + 12 = 15，所以G中不存在简单的从s到t的简单路径，长度至少为K。 b $ b

或者它满足以下条件吗？

给定一个简单的路径，我们可以很容易地检查它的长度是否至少为K（通过简单地计算

编辑2 ：你能否再解释一下为什么？我们用多项式将哈密尔顿路径问题简化为这个问题通过将所有边的长度设置为1来设置K = | V | - 1？

编辑3 ：假设我们有问题A和问题B，并且知道B是NP完全的。如果我们想证明A也是NP完全的，那么我们是否以这种方式改变A的数据，使得我们与问题B有同样的问题，因此我们推断A也是NP完全的？还是我理解错了？

编辑4 ：我们又如何证明如果图是有向和无环的，那么问题可以在时间O（| V | + | E |）？

编辑5 ：哈密尔顿路径的所有边长等于1，对吗？如果我们有V个顶点，最长路径的长度是V-1，是吗？但在我们的问题中，边缘的长度并不是特定的，K也不是固定的数字。因此，如果我们将所有边的长度设置为1并设置K = | V | - 1，我们不要把我们的问题归结为哈密顿路径问题吗？或者我理解错了？

解决方案

1. ，我们需要证明它可以用多项式时间来验证。给定一个证书（在这种情况下是一条简单的路径），我们可以很容易地检查它的长度至少是K（通过简单地计算其中所有边的长度之和）。因此，它是在NP中。



2. 对这里的多项式时间缩减感兴趣）并解决它以解决原始问题。那么我们如何在多项式时间内将哈密尔顿路径问题减少到这个问题呢？这非常简单：我们可以将所有边的长度设置为1，并设置 K = | V | - 1 。然后，我们应该尝试图中的所有顶点对，如果这个问题的解决方案对于至少一对返回真，返回真正。否则，我们应该返回false（检查我们有一个长度 | V | - 1 的路径，其中所有边的单位长度与检查的长度完全相同哈密​​尔顿路径的定义存在）。

Longest Path

We have a graph G=(V,E), lengths l(e) in Z^(+) for each e in E, a positive integer K and two nodes s,t in V.

The question is if there is a simple path in G from s to t of length at least K ?

• Show that the problem Longest Path belongs to NP.
• Show that the problem Longest Path is NP-complete, reducing Hamiltonian Path to it.
• Show that if the graph is directed and acyclic then the problem can be solved in time O(|V|+|E|).

Could you give me a hint how we could show that the problem belongs to NP? Also, how can we reduce a problem to an other, in order to show that the latter is NP-complete?

EDIT:

So in order to show that the problem belongs to NP, do we have to draw a simple and count the sum of the lengths of the edges?

Do we say for example the following?

We see that the length of the path from the node s to the node t is equal to l((s,w))+l((w,t))=3+12=15, so there is no simple path in G from s to t of length at least K.

Or does it suffice the following?

"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."

EDIT 2: Also could you explain me further why we reduce the Hamiltonian path problem to this one in polynomial time by setting all edges' lengths equal to one and set K = |V| - 1 ?

EDIT 3: Suppose that we have a problem A and a problem B and it is known that B is NP-complete. If we want to show that A is also NP-complete, do we change the data of A in that way so that we have the same problem as the problem B and so we deduce that A is also NP-complete? Or have I understood it wrong?

EDIT 4: Also how can we show that if the graph is directed and acyclic then the problem can be solved in time O(|V|+|E|)?

EDIT 5: All edges'lengths of a Hamiltonian path are equal to 1, right? And if we have V vertices, the length of the longest path is at V-1, yes? But in our problems, the lengths of the edges aren't specific and K is also not a fixed number. So if we set all edges' lengths equal to one and set K = |V| - 1, don't we reduce our problem to the Hamiltonian path problem? Or have I understood it wrong?

解决方案

1. To show that a problem is in NP, we need to show that it can be verified in polynomial time. Given a certificate(a simple path in this case), we can easily check that it length is at least K(by simply computing the sum of lengths of all edges in it). Thus, it is in NP.

2. Reduction from A to B means: given an instance of A, create an instance of B(to be more precise, we are interested in polynomial time reduction here) and solve it in order to solve the original problem. So how can we reduce the Hamiltonian path problem to this one in polynomial time? It is pretty straightforward: we can set all edges' lengths equal to one and set K = |V| - 1. Then we should try all pairs of vertices in the graph (s, t), s != t and if the solution for this problem returns true for at least one pair, return true. Otherwise, we should return false(checking that we have a path of length |V| - 1 in a graph where all edges have unit length is exactly the same thing as checking that a Hamiltonian path exists by its definition).

这篇关于如何证明prob在NP中，并且是NP-complete的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！