更新时间：2022-08-25 15:32
P/NP问题是在理论信息学中计算复杂度理论领域里未被解决的问题，也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克（Stephen A. Cook）和Leonid Levin相对独立地提出了下面的问题，即复杂度类P和NP是否是恒等的（P=NP?）。
复杂度类P即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有可以在多项式时间内验证它的解是否正确的决定问题组成，或者等效的说，那些可以在非确定型图灵机上在多项式时间内找出解的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的：P和NP相等。
在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和所接受的公理独立，所以不可能证明或证否。
用确定的图灵机以多项式时间界可解的问题称为P类问题；用不确定的图灵机以多项式时间界可解的问题称为NP类问题。
所谓P类和NP类，都是指问题的集合。由于确定的图灵机可以看作不确定的图灵机的一种特殊情形，因此这两类问题的集合之间存在子集关系，即P属于NP。
NP-完全问题( Np-complete problem)是计算复杂性理论中最重要的一部分内容。在计算科学和计算机科学理论中，NP完全问题也有着十分重要的地位。因为其重要性,NP-完全问题理论已发展成为一个独立的学科分支。
粗略地说,NP完全问题是这样的一大类问题：如果对该类中的某一个问题设计出多项式时间复杂性的电子计算机算法，那么该类中的每一个问题也都存在多项式时间复杂性的电子计算机算法；反之,如果证明了该类中的某一个问题不存在多项式时间的电子计算机算法，那么该类中的所有问题也不可能存在多项式时间复杂性的电子计算机算法。
虽然NP完全问题的研究目标是为了确定一大类问题是否存在多项式时间复杂性的电子计算机算法，但在研究方法和手段上,还是借助图灵机这种计算模型。具体地说,确定的图灵机和不确定的图灵机在计算复杂性上的差异是NP-完全问题研究的出发点。
矩阵乘法是一个P类问题。对两个n阶方阵的乘积，即使采用求内积分别求积矩阵中各个元素的方法，其时间界也只有(n3)，如果采用矩阵乘法的 Stressen算法或凝聚算法,，则可以使时间界进一步降低。
多项式求值问题是一个P类问题。若采用 Horner算法对n次多项式求值,其时间界是n的线性函数。线性函数是一次多项式函数。
查找问题是一个P类问题。在n个有序的数集合{a1,a2,…,an}中查找一个数b，若采用二分查找算法，其时间复杂度仅为(log2n)，这是比线性时间界还要低得多的一个复杂度，当然也是多项式时间界的。
P类问题还有许多，不再一一列举。
大多数理论计算机科学家相信P≠NP,是因为他们确实找到一类问题NPC，这类问题有令人非常惊奇的性质，即如果NPC中任何一个问题能够在多项式时间内找到最优解，则NP中的每个问题都能在多项式时间内找到最优解，即P=NP。尽管研究了大半个世纪，但是还没有找到任何一个NPC问题的多项式时间算法。在给出NPC的定义之前，我们先介绍问题约简的概念。
直观地，如果一个问题Q的任一实例能够容易地转化为另一个问题Q'的一个实例，则说问题Q能够约简到问题Q，这样问题Q'实例的解就可以看作问题Q相应实例的解。例如解线性方程的问题可以约简到解二次方程。例如线性方程的一个实例ax+b=0可以转化为二次方程的一个实例0x2+ax+b=0，这样实例0x2+ax+b=0的解就是实例ax+b=0的解。这样问题Q能够约简到问题Q,从某种意义上说，Q不会比Q'更难解。
虽然百万美元的奖金和投入巨大却没有实质性结果的大量研究足以显示该问题是困难的，但是还有一些形式化的结果证明为什么该问题可能很难解决。
最常被引用的结果之一是设计神谕。假想你有一个魔法机器可以解决单个问题，例如判定一个给定的数是否为质数，可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P=NP和P≠NP二者都可以证明。这个结论带来的后果是，任何可以通过修改神谕来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们为相对化）。
如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P=NP问题。