P!NP问题

本质上,在一组NP或不确定多项式时间的问题中,答案可以用多项式时间来验证。问题是所有这些问题是否都可以 确定的 在多项式时间。

如果p=np是真的,并且发现了许多难以解决但易于验证的问题,如证明,那么解决起来就和验证一样容易。

假设你有巨大的相似性——无论你想要什么。然后,您可以同时生成所有可能的解决方案,检查其中哪些是正确的,并输出正确的解决方案。在无限并行的情况下,这是一种生成解的方法。NP中的一组问题是这个过程能够快速工作的问题,因为它执行的唯一有趣的计算步骤是检查解决方案是否正确,并且这对于NP中的问题是有效的。注意,对于其他一些问题,即使这种并行性也不允许我们快速找到解决方案,因为它要求检查解决方案很容易。

但我们没有无限的平行性。我们能用一个多项式的开销来模拟它吗?如果是这样的话,我们可以想象运行上述过程,并有效地为每个易于验证的问题找到解决方案。这是P与NP的问题。

从直觉上看,答案是“不”(即P!= NP)。我们怎么可能模拟无限的并行性呢?几乎每个专家都相信这一点。但如何证明这一点是个谜,价值1000000美元的奖金。

假设我被魔术师交给一个“困难”问题的解决方案,我可以很容易地验证这个解决方案是否正确。但是,我能自己轻松地计算出这个解吗?(多项式时间)

这正是问题所在。

它可能相关,也可能无关。

人们之所以关心NP问题,是因为我们一直都想快速解决这些问题,但到目前为止,我们还没有找到快速解决这些问题的方法。我们想知道是否有快速解决问题的方法,或者我们是否应该放弃尝试。

This problem has been solved today!

(可能)

P 是所有语言中的一类,可由确定性图灵机在多项式时间内计算。现代计算机与确定性图灵机非常相似,只是图灵机的内存基本上是无限的。出于实际目的,这种区别通常被忽略。

NP 是所有语言的类,可以用多项式时间计算 不 -确定性转向机。一个不确定的图灵机不符合任何现实世界的设备。

计算复杂性的一个基本事实是 NP 相当于验证问题所在的语言类 磷 . 事实上, NP 有时定义为此类;这两个定义是可互换的,验证定义与现实世界中的确定性图灵机(如计算机)直接相关。

所以 NP 是一类在“真实”机器上多时间可验证的问题,在非常相似的理论机器上多时间可解决的问题。因此,可解性和可验证性问题是联系在一起的。

现在,大多数计算机科学家相信 磷 和 NP 是 不 等价的;也就是说,存在可由非确定性图灵机而不是确定性图灵机在多时间内计算的语言,或者不可由确定性图灵机在多时间内求解但其解可由确定性图灵机在多时间内验证的语言。

不过这里没有直接的关系。可能会有一种直观的感觉,验证一个答案比生成一个答案容易,因为作为任何一代人的一部分,都可以确保答案是正确的。因此,我们可以采用一种蛮力的方法尝试不同的解决方案,但这往往会导致指数复杂性超过p,这就是我多年前从复杂性课程中回忆到的。

他们是否有关系是克莱普尔基金会的“千年问题”之一,他们会给一百万美元的人提供一个适当的证据,坚持在几年的紧张审查。

问题的类型比它们看起来更相关,因为NP问题的另一个定义是可以用任意并行计算机有效解决的定义。

人们真正感兴趣的一件事是缺乏证据。有证据证明类似的问题,但不是这个问题。这引起了人们的兴趣,尤其是数学家,因为一个证据可能会给其他事物带来很多洞察。这显然是佩雷尔曼对庞加莱猜想的证明,这是另一个千年问题。

另一个问题是这可能产生的影响。现在,很少有人相信有一种有效的方法来解决NP完全问题,所以发现了P!NP的实际影响很小。发现一种有效的解决NP完全问题的方法将彻底改变许多计算机科学。它将使许多事情变得更容易,并通过使解密变得容易而破坏我们所知道的密码术。