在整个计算机科学中最重要的问题：P是否等于NP？
关于这个问题的正确的答案是什么？我们仍然不知道，但是大多数计算机科学家认为P不等于NP。原因主要是哲学上的，但也有证据表明，如果P等于NP，则会发生很多奇怪的事情。
P对NP问题是Steve Cook于1971年首次提出的。“P/NP问题”的P指多项式时间（Polynomial），一个复杂问题如果能在多项式时间内解决，那么它便被称为P问题，这意味着计算机可以在有限时间内完成计算； |
计算机科学就是寻找解决难题的巧妙方法。我们为其中的一些算法找到了巧妙的算法：对事物进行排序，找到最短路径，求解方程式，模拟事务...。
但是有些问题似乎太难了，一个例子是旅行问题。
查找从您的家乡城市出发的自驾车之旅，希望访问您所在国家/地区的所有主要城市，但是必须以最低的燃油费用返回家中。
这是我们希望计算机轻松解决的问题，对吗？那就是计算机的用途！
好吧，非常聪明的人已经尝试过了，没有人想出一种总是比简单地尝试所有可能的循环更好的算法。
问题在于，循环数的增长速度总是快于城市的增长速度！
让我们更加轻松一些，如果我简单地问：
是否可以旅行所有燃料费少于X美元的城市？
尚无人知道一种算法，可以精确地针对任何X值回答该问题，而无需尝试所有循环，而这又是指数级的。
那么，我们是否很愚蠢？还是这个问题太复杂了，以至于在一般情况下不可能找到一个聪明的算法来解决它？这是所有计算机科学中最重要的问题的根源：P vs NP。
回答这个问题比看起来要困难得多，您会看到，CS中的大多数问题都与事物有关：如何排序，如何比较，如何处理...
但这是一个元问题：
关于是否存在本质上很难解决的事物问题？
斯蒂芬·库克（Stephen Cook）在计算机科学的早期试图回答这个问题。他提出了以下定义：
假设我们有一个形式的问题：
是否存在具有指定属性Q的对象X？
现在来看看这个问题的回答难度。以下是这种类型的简单问题的一个示例：
给定一个由N个元素组成的数组，是否有一个元素小于X？
回答这个问题很容易。逐个查看每个元素，然后将其与X进行比较。对于任何可能的数组，该过程最多需要N个步骤。
这是P中问题的一个示例。P在这里表示“多项式时间复杂度”。直观地讲，如果存在一种算法可以在多项式时间内计算出正确的答案，那么它属于P问题。
现在回到旅行推销员，假设我给您一个答案：
是的，这是一个燃料成本小于X的循环。
您如何验证答案的正确性？您只需累计循环中所有边/路线的成本。这会再次需要N步计算才能得到答案。
下面这是NP问题的一个例子。此处的NP表示“不确定的多项式-时间复杂度”。直观上，如果存在一种算法可以验证多项式时间的正确答案，则属于NP问题。
P问题很容易解决。NP问题，我们尚不知道，但至少它们很容易验证，这是关键的。
请注意，P问题也是NP。
现在，P与NP问题正式是这样的：
NP中是否存在P中没有的问题？
P vs NP基本上是在问：是否存在天生难于解决的问题，而与我们未来的聪明程度无关。
正确的答案是什么？我们仍然不知道，但是大多数计算机科学家认为P不等于NP。
原因主要是哲学上的，但也有证据表明，如果P等于NP，则会发生很多奇怪的事情。
这个问题是计算机科学的核心，因为它讨论了计算的本质及其固有的局限性，无论技术如何改进。