复杂度类

NP 类问题的定义：- 所有基于决策的问题集合都属于 NP 问题，这些问题无法在多项式时间内解决或产生输出，但可以在多项式时间内验证。NP 类包含 P 类作为其子集。NP 问题难以解决。

注意：- 术语 "NP" 并不意味着 "非多项式"。最初，这个术语指的是 "非确定性多项式"。它意味着根据一个输入，将产生多个输出。

P 类问题的定义： - 所有基于决策的问题集合都属于 P 问题，这些问题可以在多项式时间内解决或产生输出。P 问题易于解决。

多项式时间的定义： - 如果我们在特定时间内，例如一分钟或数小时内，根据给定的输入产生输出，这被称为多项式时间。

非多项式时间的定义： - 如果我们根据给定的输入产生输出，但没有时间限制，则称为非多项式时间。但是，输出将产生，但时间尚未确定。

基于决策的问题的定义： - 如果一个问题的输出是一个简单的 "是" 或 "否"（或者你可能需要将其视为真/假，0/1，接受/拒绝），则该问题被称为决策问题。我们将许多优化问题表述为决策问题。例如，贪婪方法、D.P.，给定一个图 G= (V, E)，是否存在任何哈密顿回路。

NP-hard 类的定义： - 为了进入 NP-hard 类的划分，您需要满足以下几点

1. 如果我们可以用多项式时间解决这个问题，那么我们就可以用多项式时间解决所有 NP 问题
2. 如果您在多项式时间内将问题转换为另一种形式

NP-complete 类的定义： - 如果一个问题是 NP-complete，那么

1. 它在 NP 中
2. 它是 NP-hard

所有 NP 类（包括 NP、NP-hard 和 NP-complete）的图示

图：复杂度类