logo标签列表

P != NP问题

computer-sciencetheorycomplexity-theory
10

虽然不是一道'纯粹'的编程问题，但由于它深度涉及编程理论，因此我认为在这里提问最好。

关于P NP 问题，来自 http://en.wikipedia.org/wiki/P_versus_NP_problem 的摘录如下： “实质上，问题P = NP？问：假设可以快速验证对一个是或否的问题的肯定答案。那么，答案本身能否也被快速计算出来？”

我想知道，验证答案的速度与生成解决方案的速度有何关系？

7
P =? NP的整个意义在于回答你的问题。 - Steven
2
那么，找出这个问题的答案不就解决了P与NP的问题吗？已经有很多信息可供您参考。查一下“哈密顿回路”吧。这是一个容易理解的例子。 - Heath Hunnicutt
3
换句话说，“是的，伙计，我们都在想同样的事情。” - Heath Hunnicutt
3
@Heath：我觉得这是一个真正的问题。它可以通过相当客观的方式回答。 - David Thornley
可能不是同一篇文章，但您可以从中的数据进行谷歌搜索：http://www.allvoices.com/contributed-news/6476401-vinay-deolalikar-explains-the-proof-that-p-np - jason
显示剩余13条评论
9个回答
5
假设你有非常强大的并行能力，无论需要多少都能得到。你可以同时生成所有可能的解决方案，检查哪些是正确的，并输出正确的解决方案。在存在无限并行性的情况下，这是一种生成解决方案的方法。NP问题集是指这个过程将快速完成的问题集，因为它所执行的唯一有趣的计算步骤是检查解决方案是否正确，而对于NP问题来说，这可以高效地完成。请注意，对于其他一些问题，即使具有此并行性，我们也无法快速找到解决方案，因为它要求检查解决方案很容易。
但是我们没有无限的并行性。我们能否以多项式量级的开销模拟它？如果可以，我们可以想象运行上述过程，并高效地找到每个验证容易的问题的解决方案。这就是P与NP问题。
直觉上，答案似乎是“不”（即P≠NP）。我们怎么可能模拟无限的并行性呢？这是几乎所有专家的看法。但是如何证明它仍然是一个谜，值得100万美元的奖金。
4
基本上，在NP（非确定性多项式时间）问题集中，答案可以在多项式时间内验证。问题是是否所有这类问题都可以在多项式时间内确定。
如果P=NP成立，并且发现了这样的算法，许多难以解决但易于验证解决方案的问题，例如证明，将变得像验证一样容易解决。
哇，非常有趣！我现在可以看到为什么会对此感兴趣了，谢谢！ - jason
这个答案不正确。NP 是指具有多项式时间验证器的问题集。这包括P中的所有问题。显然，如果你有一个多项式时间的正确求解器，你也有一个多项式时间的验证器。问题是是否存在NP中的问题，而这些问题并不在P中。 - Borealid
@Borealid：根据你的说法，我更正了我的答案（我一开始想的是NP完全问题）。 - murgatroid99
1
“变得像验证一样容易解决”对我来说是一个“恍然大悟”的时刻。 - jason
2
假设一个魔术师给我一个“难”问题的解决方案，我可以轻松地验证这个解决方案是否正确。但是，我能否自己轻松地计算出这个解决方案？（多项式时间） 这正是问题所在。
1

这可能与编程有关，也可能与之无关。

人们关心 NP 问题是因为我们希望能够快速解决它们，但迄今为止我们还没有找到快速解决它们的方法。我们想知道是否有一种快速解决它们的方法，或者我们应该放弃尝试。

1
也许吧。我既没有多个学科的深入知识来验证它，也没有渴望去阅读一百页的证明。我认为我们应该让专家们讨论几年，看看他们会说什么。 - David Thornley
遗憾的是，不行。尽管这引起了很多媒体关注，但这最新的证明尝试与之前的（许多）其他尝试一样有缺陷。 - Aaron
@David＆Aaron：是的，这完全超出了我的理解范围。相差甚远。 - Andy
更多详细信息请参见此处：http://www.theregister.co.uk/2010/08/11/the_p_versus_np_problem/，其中包括有关问题更简单解释的有用链接：http://www.claymath.org/Popular_Lectures/Minesweeper/。 - Richard
0

它们是否相关是Claypool基金会的“千年难题”之一，他们将向提供经过数年深入研究的适当证明的人提供一百万美元。

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

有一件事情真正引起人们的兴趣，那就是缺乏证据。类似的问题已经有证明了，但这个问题没有。这让人着迷，特别是数学家，因为一个证明可能会带来很多其他东西的见解。这显然适用于佩尔曼关于庞加莱猜想的证明，这也是Millenium难题之一。

另一个问题是这可能会产生的影响。目前，很少有人相信有一种有效的方法来解决NP完全问题，因此发现P！= NP对实际影响不大。发现一种有效的方法来解决NP完全问题将彻底改变计算机科学。这将使许多事情更容易，并通过使解密变得容易而摧毁我们所知道的加密技术。

1
Perelman 证明了 Poincare 猜想，而不是 Riemann 假设。 - Aaron
@Aaron：非常感谢。正在适当地编辑。 - David Thornley
0

P 是所有可以由确定性图灵机在多项式时间内计算的语言类。现代计算机非常像确定性图灵机，只是图灵机本质上具有无限的内存。这种区别通常在实际应用中被忽略。

NP 是所有可以由非确定性图灵机在多项式时间内计算的语言类。非确定性图灵机不对应于任何真实世界的设备。

计算复杂性的一个基本事实是，NP等价于其验证问题在P类中的语言类。事实上，NP有时被定义为这个类；这两个定义是可互换的，而验证定义具有直接与现实世界中的确定性图灵机类似的计算机的相关性。

因此，NP是可以在“真实”机器上进行多项式时间验证并且可以在非常相似的理论机器上进行多项式时间求解的问题类。因此，可解性和可验证性的问题是相互关联的。

现在，大多数计算机科学家认为P和NP是不等价的；也就是说，存在一些语言可以被非确定性图灵机在多项式时间内计算，但不能被确定性图灵机计算，或者等价地说，这些语言不能在确定性图灵机上以多项式时间解决，但它们的解可以被确定性图灵机在多项式时间内验证。
0

虽然这里没有直接的关系。但是可能会有一种直觉感觉，验证答案比作为生成的一部分生成答案更容易，因为生成答案需要确保答案正确。因此，可以采用暴力方法尝试不同的解决方案，但这往往会导致超出P的指数复杂性，或者这就是我几年前在复杂度课程中记得的。

0

不，P≠NP。

答案是Co-NP-Asymmetric-Partially-Complete。

请到我的网站查看完整答案：

https://singularitariantechnologies.wordpress.com/exponential-breakthroughs-in-epistemology-every-week/

Singularitariantechnologies.wordpress.com

简单总结一下你的问题的答案，通常情况下是不行的，除非P=NP，因此共np-不对称部分不完整/完整的答案。

为了做到这一点，我使用Google.com作为数据库，可以在多项式时间内给我一个验证过的答案，然后我想看看是否可以根据最佳公理化约简来计算答案，其中包括指数项，本质上，即使我们知道验证过的答案是什么，但如果有两个以上的变量（在这种情况下是指数），答案也是无法计算的。

显然，这让黑客们没有其他选择，因为未来的加密算法将不会那么简单。此外，从公理上讲，多项式必须由多个术语组成，因此当变量>=3时，P=/=NP，当变量<=2时，P=NP，这只是一个实例。

请阅读我的网站或Google Drive上的完整文档，我还提供了一个电子表格链接，链接到我的singularitariantechnologies.wordpress.com上的工作。

这句话的意思是什么？未来将不会有黑帽子式的攻击，即使你试图通过模二公理化减少加密攻击，也无法在高级加密（复杂多项式加密，带有一些附加条件和花哨的功能，使破解密码或任何加密数据变得更加困难）中奏效。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接