algorithm - NP问题，需要一些细节？

Question

我看到一个关于算法的解决方案。以下哪个属于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?

谢谢。

Answer 1

他们都是NP，因为:

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

2. 它在 P 类中(我认为多项式时间解是显而易见的)，这自动意味着它在 NP 中。

3. 同样，存在多项式时间解，这意味着它在 P 中。因此，它在 NP 中。

4. 给定一个适当的子集，我们可以在多项式时间内验证它。因此，根据定义，它属于 NP。

关于0/1背包问题的判定版本:它是NP。它也被称为 NP-complete(证明太长无法写在这里，这里是链接:proof)。这也意味着它是 NP 难的(根据定义，任何 NP 完全问题都是 NP 难的)。

附言我假设“寻找最大流量”在这里意味着决策版本。