把两个N位数相乘的标准方法涉及N^2个基本的整数对乘法，最多再加上处理进位的N个加法。一共最多有N^2＋N个基本运算。注意到表达式N^2＋N的值总是小于N^2＋N^2，即2N^2。于是，两个N位数相乘所涉及的基本运算少于2N^2个。
加法就是所谓"线性时间过程”的一个例子。一个线性时间过程是对规模为N的数据，至多需要C×N个基本步骤来完成的过程，这里C是某个固定的数（在心算加法的情况中，C=3）。
我们可以假定，任何基本运算都需要相同的固定时间，那么基本步骤的数目就直接对应于计算所花的时间。
词组“线性时间”中的“线性”是指，如果你画出步骤数目与数据规模之间关系的图像，那将是一条直线。（直线的方程式将是S=CN，S是步骤数目。）
相应地，乘法是一个"平方时间"过程。一般来说，如果一个过程对规模为N的数据至多需要C×N^2个步骤来完成，其中C是某个固定的数，那么它就被说成是以平方时间运行。
一个比线性时间过程和平方时间过程更为一般的概念是“多项式时间过程”，一个多项式时间过程是对规模为N的数据至多需要C×N^k个基本运算的过程，其中C和k是某两个固定的数。
当面对一个计算过程时，理论工作者就寻找这样一个代数表达式（例如CN、CN^2或CN^k），它能给出这一过程对于规模已知为N的数据来说，所需要的基本步骤数目的一个上界估计。他们称这样的表达式为这个过程的"时间复杂性函数"。多项式时间过程是以多项式表达式为时间复杂性函数的过程。
多项式时间对指数时间大致而言，多项式时间过程是计算机能有效处理的一种过程。如果那两个固定的数C和k都十分巨大，那么计算时间可达数亿年。不过在实际上，日常生活中往往会产生的多项式时间过程所具有的C和k的值是完全适度的，k一般是个一位数，因此它们确实能被计算机有效地处理。
还有一个类型称为“指数时间过程”，当数据规模为N时，需要2^N个基本步骤来完成的过程（底数也可以是某个大于2的数）。
指数时间过程几乎无法在计算机上运行，因为随着N的增大，步骤增加速度太快。如果在一个国际象棋盘上以2^N的规律放硬币，那么最后一格硬币的高度能一直伸到半人马座的比邻星（37万亿千米）。
对于在工业和商业中产生的几乎所有的指数时间过程，即使要处理规模相当适度的数据，也要让世界上最快的计算机花上比宇宙寿命还要长的时间。
显而易见，如果对于一个特定的问题，你所知道的唯一解决方法是使用指数时间过程，那么你将不可能解决这个问题，除非数据规模非常小。
NP问题多项式时间过程与指数时间过程之间的鸿沟也说明了这种分类的一个明显缺点∶它太过粗略了。数学家意识到了这一点后，便寻找中间尺度的过程复杂性。他们注意到，对于像求解推销员问题的过程来说，困难并不是由于复杂的计算。使得问题几乎无法解决的原因，是需要检查的可能性的数量之多，使得完成全部过程所需要的时间长得令人绝望。
为了试图把这种过程与一种真正复杂计算的过程区分出来，数学家提出了第三种类型∶非确定性多项式时间过程，或简称NP过程。由于通常的计算机都是确定性的，所以采用“非确定性”这个词会给人们一个暗示，即这个新概念是一个理论的东西，与实际的计算基本无关。下面是它的大致思想。
设想你有一台这样的计算机，它能在一次计算的某些阶段从许多备选的数中作出一个完全随机的选择。比方说，当面对推销员问题的一个具体例子的时候，这台计算机能从这位推销员可以走的所有可能的路线中随机地选出一条。为了解出这个问题，这台计算机选出一条路线并算出相应的总距离。这条选出的路线不是最短路线的概率是极大的。但假定这台特别的计算机具有好得不可思议的运气，使得它总是作出最佳的选择。于是它会在多项式时间内解决这个问题。作出一个随机猜测并能幸运地猜中的本领，使得我们避开了可能性的数量大得令人绝望这个难题。
一般说来，如果一个问题或任务可以用一台非确定性计算机在多项式时间内解出或完成，我们就说它是NP型的，而非确定性计算机就是能从一系列备选对象中作出一个随机选择而且能极其幸运地选中的计算机。
从直觉上说，NP问题介于多项式时间问题（简称P问题）与指数时间问题之间。因为NP概念建立在一个完全不现实的想法上，即有一种计算机能老是作出最佳的随机选择，所以它是纯理论的。然而它显示出相当大的重要性。一个理由是，在工业和管理中出现的大多数指数时间问题都是NP型的。使得它们很难解决的原因并不是有关的计算很复杂，而是必须对极其大量的实质上相同的情况重复执行一种相对容易的计算。
当NP分类于20世纪60年代第一次被提出时，计算机科学家臆断P类与NP类并不是同一个类——虽然每个P问题当然都是NP问题，但是有一些NP问题肯定不属于P类。理由是，看来一台运行多项式时间算法的标准计算机无论如何也不可能表现得像一台想象的非确定性计算机作准确猜测时那样。例如，专家们认为，如果没有一台假想的非确定性计算机的准确猜测能力，推销员问题也许根本不可能在多项式时间内解决。
人人都认为这只是个时间问题∶迟早有人会给出某个可证明不属于P类的NP问题——不是推销员问题，就是其他什么问题——从而证明P和NP是不同的问题类。但这件事至今没有发生。也没有人能证明相反的结论。于是，P对NP问题产生了。
20世纪60年代后期，这个问题已相当重要。工业与管理中的许多重要问题都被证实是NP问题。如果能证明P就是NP，那无疑将激发人们以极大的努力去找出解决这些重要问题的有效过程。
这时，库克登场了。库克证明存在一个特殊的NP问题，它具有一种奇特的性质∶如果这个特殊的问题能用多项式时间过程解决，那么其他任何的NP问题也能。这是一个关于什么类型的任务可以在一台非确定性计算机上执行的问题。
库克证明其结论的方法是∶他显示了怎样可以将任意给出的NP问题转化成他这个特殊的问题，这样，如果他这个问题能在多项式时间内解决，那么通过转换，那个给出的NP问题也能。库克将这个性质命名为NP完全性。根据库克的定义，对于一个NP问题，如果发现了一个可以解决它的多项式时间过程将意味着，NP类中的每一个问题都可以用一个多项式时间过程解决，则这个NP问题被称为NP完全的。
虽然库克的问题是一个来自形式逻辑的高度理论性的问题，但没过多久，卡普等人就证明了其他许多更为令人熟悉的NP问题也具有这个NP完全性，其中包括推销员问题。
对工业界人士而言，发现能解决诸如推销员问题的有效过程就意味着利润大幅增长。这并不是说NP完全性就意味着一个问题肯定不能有效地解决。准确点说，证明一个特定的问题是NP 完全的，就对它的难度，以及你将找到一个多项式时间过程来解决它的不可能程度给出了一个尺度。下面解释一下。
现在假设你发现你的NP问题事实上是NP完全的。那么大多数专家就把此作为一个不值得花费时间和精力来为它寻找一个完整解的充足理由。他们转而把自己的精力用在寻找一个好的近似通解上。因此，尽管NP分类具有高度的人为性质，但它的确有助于管理者决定把他们的研究精力投在什么地方。
但是未被解决的P对NP问题依然潜伏在每一件事情后面。一个关于P与NP相同的证明将在原则上使得关于NP 完全性的所有研究都变得徒劳。这样的证明还会对互联网的安全产生严重的后果。因为破译RSA密码是一个NP问题。人们还不知道RSA加密系统的破译问题是不是NP完全的（很可能不是），因此，用不着证明P与NP相同，也许就会研究出这个问题的一个多项式时间解法。而另一方面，如果证明了P与NP相同，那么立即就说明RSA系统的破译问题可以在多项式时间内解决。那样的话，整个互联网的安全系统将处于极不可靠的状态。
P vs NP
