这个看似简单的一个问题，实际上是理论计算机领域最大的未解难题。2000年，在参考了一个世纪前希尔伯特提出的23个问题的做法之后，克雷数学研究所发布了七道千禧年大奖难题，总价值七百万美金。解答出任何一道问题的第一个人将被授予一百万美金的奖励。其中一道难题正是关于解决P和NP的复杂度问题。这个问题成为了整个计算机领域的焦点，因为这个问题的结论会直接给计算机领域带来截然不同的理论极限和发展前景。
虽然从表面上看，P是否等于NP这个问题非常直接，但它的证明却已困扰了研究人员长达数十年之久。简单地说，P与NP问题问的是，能够被容易解决的问题集合是否也属于能够被容易验证的问题集合中。让我们来试想一个场景，假设你接收到了一项任务，内容是将一个打碎的茶杯重新粘合在一起。要想检验你是否成功地完成了这项任务是非常简单的——如果成功了，你的面前就会有一个完整的茶杯。
但是，将每一块散落的碎片重新粘合起来是件很困难的事。这就是NP问题的一个例子：难解，却容易验证。
假如现在你的任务不是重新粘合破碎的茶杯，而是计算茶杯被打碎成了多少块。这就变成了一个P类问题。相比之下，计算碎片的数量比计算它们之间的联系要容易得多。当委派给计算机一项任务时，计算机算法需要一定的时间来解决它。那么，如何理解一个算法解决问题需要花费的时间呢？
举个例子，假设你有一个未经排序的数字列表，你想写一个算法来找出其中最大的数。这个算法必须查看列表中的所有数字，这是无法避免的。但是，如果它只是记录到目前为止看到的最大数字，那么每个数字只需被查看一次。因此，算法的执行时间与它处理的单元数量成正比——计算机科学家称其为N。
由于有些算法的效率会比其他的算法效率更高或更低，所以它们完成的时间可能与N、N²、N³……有关。
其中的关键在于指数是一个常量——1、2、3等等。在这种情况下，算法被称为在是多项式时间内完成的，或简称为P。如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P类问题。但可惜的是，并不是所有的问题都这样。一些问题的解决需要花费的时间正比于2ᴺ、3ᴺ……在这种情况下，N是指数，这意味着算法要处理的每个单元的复杂度都呈指数级增长。
在这种情况下，算法可以在指数时间内完成，或简称为NP（它实际上意为不确定性多项式时间）。
这二者之间可以有非常巨大的差别。举个例子，假如一个有100个单元的P算法，它完成工作的时间长度正比于N³，解决问题所需的时间大约是3小时；但如果它是一个NP算法，完成任务的时间与2ᴺ成正比，那么它花费的时间可以达到约3亿亿年。问题“P是否等于NP”的另一种问法是，每一个困难问题是否都包含一个简单但隐藏的解。这两种类型的问题是否不可避免地彼此分离？是否一些问题的本质就是复杂的？
如果P确实等于NP，那么它对我们的生活将产生重大影响。一个主要的好处是，许多NP问题被称为NP完全问题，这意味着它们的解可以迅速适用于任何其他NP完全问题。因此，找到一种快速解决一个NP完全问题的方法，将在解决所有其他NP完全问题方面取得重大进展。虽然如果P=NP成立的话，我们将失去表面上的互联网安全，造成损失惨重的后果，但它也将产生许多有益的后果。
科学共识不过，大多数计算机科学家并不相信P=NP。根据2001年的一项调查显示，有61%的人相信P≠NP；而2012年的调查则显示，相信P≠NP的人达到了83%。