P 与 NP

P 类

P 类问题是单带确定 TM 在多项式时间内可判定的问题, 即 $P={\bigcup }_{k}TIME(n^k)$.

• 对于所有与单带确定 TM 等价的模型, P 不变.
• P 大致对应于在计算机上实际可解的问题, 研究的核心是一个问题是否属于 P 类.

指向原始笔记的链接

NP 类

$NTIME(t(n))=\{L|L\text{可被}O(t(n))\text{时间NTM判定}\}$

NP 类问题是单带非确定 TM 在多项式时间内可判定的问题, 即 $NP={\bigcup }_{k}NTIME(n^k)$.

指向原始笔记的链接

P=成员资格可以快速判定的语言类; NP=成员资格可以快速验证的语言类.

显然 $P\subseteq NP$, 但未能证明 $P=NP$.