前言

根据算法的时间复杂度,我们可以把算法问题划分为几大类问题:

  • P 问题
  • NP( non-deterministic polynomial ) 问题
  • NPC (Non-deterministic Polynomial complete problem) ( NP完全问题 )
  • NPH (Non-deterministic Polynomial hard problem) ( NP难问题 )。

具体描述如下。

P 问题

P 问题属于确定性多项式问题,该类问题能在多项式时间( Polynomial Time ) 内找出解。何谓多项式时间呢?

我们设解决该问题的算法所对应的时间复杂度为: $$ F(n) $$。$$ F(n) = log(n), F(n) = n^a $$ 等形式则表示算法具有多项式级复杂度。对应的诸如 $$ F(n) = a^n, F(n) = n! $$ 等则是指数级复杂度。

NP 问题

首先, P 问题属于 NP问题。

NP 问题指该问题 不一定 有确定性多项式解法,以及我们 不一定 能在多项式时间内找出解,但是在我们举出问题的一个解后 一定能在多项式时间内验证该解是否正确

NPC ( NP完全问题 )

叙述 NPC 问题前,先了解一个概念 “约化” (reducibility) ,也叫 “归约” 。如果能把 求解 A问题 变为 求解 B问题,则可以说 A问题能约化到B问题,或 A问题能归约到B问题,其中求解 B问题的难度大于求解 A问题的难度。一个典型的例子是:求解一元一次方程可以约化为求解一元二次方程,所做的变动为添加 $$0 * y = 0$$. 切记,不要把约化理解成化简了,实际上是化复杂

NP 完全问题指的是在某一类 NP问题中,存在一个问题 Y,使得所有该类的 NP问题都可以归约到 问题Y 上来。这个问题 Y 就是 NP完全问题。只要找到了这个问题的解法,那么该类中所有的 NP问题就都可以找出解。

NPH( NP难问题 )

NPH 问题比 NPC问题的定义更宽泛,NPC 问题属于 NPH问题。

假设存在一个 NPH 问题 H,该类中的所有 NP问题也都能归约到问题 H。但 H不一定属于 NP 问题,即不一定满足 能在多项式时间内验证解 这个条件。

以上。

标签: 算法

添加新评论