【知识】NP及其相关问题的概念

转载请注明出处：小锋学长生活大爆炸[xfxuezhagn.cn]

如果本文帮助到了你，欢迎[点赞、收藏、关注]哦~

NP问题

1. P 类问题

2. NP 类问题

3. NP-Complete 问题

4. NP-Hard 问题

5. NP-Hardness

例子 🌟

其他问题

1. co-NP

2. PSPACE

3. EXPTIME

4. BPP (Bounded-error Probabilistic Polynomial time)

5. Σk和Πk类 (Polynomial Hierarchy)

6. L 和 NL (Logarithmic Space)

7. APX

8. FPT (Fixed-Parameter Tractable)

9. #P (Sharp-P)

10. W类 (Parameterized Complexity)

例子

NP问题

1. P 类问题

P (Polynomial time)：指的是能够在多项式时间内被确定性图灵机解决的问题。这类问题通常被认为是“容易”或“可解”的，因为存在有效的算法。例如，排序算法（如快速排序）和图的最短路径问题都属于P类问题。

2. NP 类问题

NP (Nondeterministic Polynomial time)：指的是能够在多项式时间内被非确定性图灵机验证的问题。这类问题的解决方案可以在多项式时间内被验证，但找到解决方案可能需要很长时间。例如，旅行商问题（TSP）和3-SAT问题都是NP问题。

3. NP-Complete 问题

NP-Complete：这是NP类中最难的问题。如果一个NP-Complete问题能够在多项式时间内被解决，那么所有NP问题都能够在多项式时间内被解决。要证明一个问题是NP-Complete，通常需要两个步骤：

证明该问题属于NP类。
证明所有其他NP问题都可以在多项式时间内归约到该问题。

例如，3-SAT问题和哈密顿路径问题都是NP-Complete问题。

4. NP-Hard 问题

NP-Hard：这些问题至少和NP类问题一样难，但不一定属于NP类。这意味着NP-Hard问题不一定是决策问题，它们可以是优化问题。即使能够验证一个NP-Hard问题的解，其验证过程也不一定在多项式时间内完成。例如，旅行商问题的优化版本是NP-Hard的。

5. NP-Hardness

NP-Hardness：这是对问题难度的一种描述，表示问题的计算复杂性至少和NP问题一样高。换句话说，如果一个问题是NP-Hard的，那么它至少和最难的NP问题一样难。

例子 🌟

P问题：快速排序，Dijkstra算法（最短路径）。
NP问题：子集和问题（SUBSET-SUM），图的着色问题。
NP-Complete问题：3-SAT问题，哈密顿路径问题。
NP-Hard问题：旅行商问题（优化版本），计算Wasserstein重心的问题。

其他问题

1. co-NP

co-NP 类问题是与 NP 类问题互补的一类问题。一个问题属于 co-NP 类，如果它的否定问题属于 NP 类。换句话说，如果一个问题的解可以在多项式时间内验证，那么 co-NP 类问题的反例（解不存在的证明）也可以在多项式时间内验证。例如，3-SAT 的否定问题是“判断一个布尔公式是否对所有赋值都不为真”，属于 co-NP 类。