通俗易懂的P vs NP问题解释 -@AlejandroPiad

21-01-08 banq

在整个计算机科学中最重要的问题:P是否等于NP?

关于这个问题的正确的答案是什么?我们仍然不知道,但是大多数计算机科学家认为P不等于NP。原因主要是哲学上的,但也有证据表明,如果P等于NP,则会发生很多奇怪的事情。

 

 P对NP问题是Steve Cook于1971年首次提出的。“P/NP问题”的P指多项式时间(Polynomial),一个复杂问题如果能在多项式时间内解决,那么它便被称为P问题,这意味着计算机可以在有限时间内完成计算;
NP指非确定性多项式时间(nondeterministic polynomial),一个复杂问题不能确定在多项式时间内解决,假如NP问题能找到算法使其在多项式时间内解决,也就是证得了P=NP
- 百度百科

 

计算机科学就是寻找解决难题的巧妙方法。我们为其中的一些算法找到了巧妙的算法:对事物进行排序,找到最短路径,求解方程式,模拟事务...。

但是有些问题似乎太难了,一个例子是旅行问题。

查找从您的家乡城市出发的自驾车之旅,希望访问您所在国家/地区的所有主要城市,但是必须以最低的燃油费用返回家中。

这是我们希望计算机轻松解决的问题,对吗?那就是计算机的用途!

好吧,非常聪明的人已经尝试过了,没有人想出一种总是比简单地尝试所有可能的循环更好的算法。

问题在于,循环数的增长速度总是快于城市的增长速度!

让我们更加轻松一些,如果我简单地问:

是否可以旅行所有燃料费少于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,则会发生很多奇怪的事情。

 

这个问题是计算机科学的核心,因为它讨论了计算的本质及其固有的局限性,无论技术如何改进。

 

              

2
猜你喜欢