算法复杂度分类

NP类问题的定义问题：-所有基于决策的问题的集合进入了NP问题的划分中, 这些问题无法在多项式时间内解决或产生输出, 但需要在多项式时间内进行验证。 NP类包含P类作为子集。 NP问题难以解决。

注意：-术语“ NP”并不表示“非多项式”。最初, 该术语表示“非确定性多项式。它表示将根据一个输入数量产生输出。

P类问题的定义：-基于决策的问题集划分为P个问题, 这些问题可以在多项式时间内求解或产生输出。 P问题容易解决

多项式时间的定义：-如果我们在给定的时间内（例如一分钟, 几小时内）根据给定的输入产生输出。这称为多项式时间。

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

基于决策的问题的定义：-如果问题的输出为简单的“是”或“否”（或者你可能需要此为true / false, 0/1, 接受/拒绝）, 则该问题称为决策问题。将许多优化问题称为决策问题。例如, 如果存在任何哈密顿循环, 则给定曲线G =（V, E）的Greedy方法D.P.。

NP-hard类别的定义：-在这里你要满足以下几点才能进入NP-hard的划分

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

NP-完全分类的定义：-如果NP-完全存在问题

1. 在NP中
2. NP难

所有NP类的图形表示, 包括NP, NP-hard和NP-complete

图：复杂度等级