NP问题，需要一些细节？ [英] NP problems and need some detail?

问题描述

我看到算法中的一个解决前。以下哪项是NP？

  TSP的）决定版

B）数组排序？

三）发现的最大流量网络

d）第0/1背包版本？
 

  

我的注意，说，所有这些是NP，任何人都可以加一点细节   每一个为什么？我混淆约0/1背包，是NP？ NP-HARD？   或NP完全？

感谢。

解决方案

他们都是在NP，这是因为：

1. 可以确认在多项式时间。鉴于一些行车路线，我们可以很容易地检查它的长度是否不超过给定值。

2. 这是P中的类（我认为一个多项式时间的解决方案是显而易见的），它会自动意味着是NP。

3. 再次有多项式时间解，这意味着它是在P对应，它是在NP

4. 我们可以在多项式时间内验证它，给予适当的子集。因此，它是在由NP定义

关于决定版的0/1背包问题：它是在NP。它也被称为是NP完全（证明太长写在这里，这里是链接：证明）。这也意味着它是NP硬的（任何NP-完全问题是NP硬根据定义）。

P.S。我认为发现最大流在这里是指决策的版本。

I see one solved ex on Algorithms. Which of the following is in NP?

a) Decision Version of TSP 

b) Array is Sorted?

c) Finding the maximum flow network

d) Decision version of 0/1 knapsack?

My Note, says all of these is in NP, anyone could add a bit detail for each one why? and I confusing about 0/1 knapsack, is it NP? NP-HARD? or NP-Complete?

Thanks.

解决方案

They all are in NP, because:

1. It is verifiable in polynomial time. Given some route, we can easily check whether its length does not exceed the given value.

2. It is in P class(I think a polynomial time solution is obvious), which automatically means that is in NP.

3. Again, there is polynomial time solution, which means that it is in P. Thus, it is in NP.

4. We can verify it in polynomial time, given an appropriate subset. Hence, it is in NP by definition.

About the decision version of the 0/1 knapsack problem: It is in NP. It is also known to be NP-complete(the proof is too long to write here, here is link: proof). It also means that it is NP-hard(any NP-complete problem is NP-hard by definition).

P.S. I assume that "finding maximum flow" means a decision version here.

这篇关于NP问题，需要一些细节？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！