P_NP_NPC

1.简介

P问题：一类可以通过确定性图灵机在多项式时间内解决的问题集合。
NP问题：一类可以通过非确定性图灵机在多项式时间内解决的决策问题集合。
**P与NP：**任何可以被图灵机在多项式时间内解决的问题都可以被非确定性的图灵机解决，不确定是否是真子集。
**NPC问题：**一个NPC问题需要同时满足两个条件。①该问题是NP问题；②NP里所有问题可以在多项式时间内转为该问题。
**NPH问题：**只需要满足NPC中的第二个性质，所以，NPC是NPH的子集。
上述元素的近似关系图：

$\mathbf{P} \subseteq \mathbf{co}-\mathbf{N} \mathbf{P}$：
①因为P在运算下封闭，如果一个语言在P中，这时他的补语言co-P也在P中。综上得P与co-P都在NP中。
②一个语言在co-NP当且仅当他的补语言在NP。综上得P与co-P都在co-NP中。
)
**补语(复杂性类)：**记为co-C。一个决策问题 X是反C的成员，当且仅当它的互补 X是在复杂类C【维基百科】。补的例子：一个重要问题是数字是否是素数，它的补充是确定一个数字是否是一个复合数，这里补语的域是超过1的所有整数的集合。这个补也许还是一个NP问题，也许不是一个NP问题。

2.结语

才疏学浅，如有不正确的言语，还请指出。