概要

1

P类问题是指在确定性图灵机上，能够在多项式时间内判定的问题类别。而NP类问题是指，当给定一个“是”的证据（称为Witness）时，能够在多项式时间内验证该Witness正确性的问题类别。由于在多项式时间内可以判定的问题，也必定能在多项式时间内被验证，因此P⊆NP是显而易见的。但P是否为NP的真子集，目前尚不明确。尽管目前尚未得到证明，但大多数研究人员都相信P≠NP。这种认为P类问题与NP类问题不相等的猜想，就被称为“P≠NP猜想”。