P=NP问题

计算复杂性理论中一个尚未解决的重要问题：确定型图灵机多项式有界时间可计算的函数类是否等于非确定型图灵机多项式有界时间可计算的函数类。

确定型图灵机就是普通的图灵机(参见图灵机)，它的每一步运算都是由上一步运算的结果唯一确定的。确定型图灵机的计算过程是链状的，可以用一个序列(例如瞬时描述的序列)来表示，序列的长度称为该计算的步数或该计算的时间消耗。

设f是一图灵可计算函数，如果存在多项式p(x)和(确定型)图灵机M，使得只要f(x)有定义，M计算f(x)的步数就不超过p(x)，则称f为确定型图灵机多项式有界时间可计算的，全体确定型多项式时间有界可计算函数的类记作P。

非确定型图灵机与确定型图灵机的不同之处在于：它的每一步运算并不由上一步运算完全决定。而是有一定的选择余地。一步运算结束后，下一步如何进行，可以有若干种(比如说两种)选择，因而其计算过程不是链状的，而是树状的。

其每个枝都相当于确定型图灵机的一个计算。因而，非确定型图灵机的计算可以看作是沿各个枝同时进行，因而也叫并行计算(相应地，确定型计算机的计算就叫串行计算)。在并行计算中，如果有一个枝有了结果(停机)，整个计算就告结束。这个枝的长度(也就是树高)称为该计算的步数(时间消耗)。

设f为非确定型图灵机可计算的函数，如果存在多项式p(x)和非确定性图灵机M，使得只要f(x)有定义，M计算f(x)的步数就不超过p(x)，则称f为非确定型图灵机多项式时间有界可计算的。全体非确定型图灵机多项式时间有界可计算函数的类记作NP。

P=NP问题就是问P和NP两个函数类是否相等。由于确定型图灵机是非确定型图灵机的特例，故P≤NP，因而P=NP问题实际上也就是问是否有NP≤P。

P=NP问题自提出至今不过二十年的时间，它一直是计算复杂性理论中的一个中心问题，许多人猜测P≠NP，但也有人猜测P=NP。近年来又有人猜测P=NP问题独立于现有的公理体系，也就是说利用现有的数学工具既不能证明P=NP，也不能证明P≠NP。不过这一切都尚未得到证明。(参见计算复杂性和NP完全问题。)