假设P ≠ NP的复杂度类的图解。如P = NP则三个类相同。 简单来说，P = NP问题问道：如果是／不是问题的正面答案可以很快验证，其答案是否也可以很快计算？这里有一个给你找点这个问题的感觉的例子。给定一个大数Y，我们可以问Y是否是复合数。例如，我们可能问53308290611是否有非平凡的因数。答案是肯定的，虽然手工找出一个因数很麻烦。从另一个方面讲，如果有人声称答案是"对，因为224737可以整除53308290611"，则我们可以很快用一个除法来验证。验证一个数是除数比找出一个明显除数来简单得多。用于验证一个正面答案所需的信息也称为证明。所以我们的结论是，给定正确的证明，问题的正面答案可以很快地（也就是，在多项式时间内）验证，而这就是这个问题属于NP的原因。
虽然这个特定的问题，最近被证明为也在P类中（参看下面的关于"质数在P中"的参考），这一点也不明显，而且有很多类似的问题相信不属于类P。 像上面这样，把问题限制到“是／不是”问题并没有改变原问题（即没有降低难度）；即使我们允许更复杂的答案，最后的问题（是否FP = FNP）是等价的。
