虽然不是一道'纯粹'的编程问题,但由于它深度涉及编程理论,因此我认为在这里提问最好。
关于P NP 问题,来自 http://en.wikipedia.org/wiki/P_versus_NP_problem 的摘录如下: “实质上,问题P = NP?问:假设可以快速验证对一个是或否的问题的肯定答案。那么,答案本身能否也被快速计算出来?”
我想知道,验证答案的速度与生成解决方案的速度有何关系?
虽然不是一道'纯粹'的编程问题,但由于它深度涉及编程理论,因此我认为在这里提问最好。
关于P NP 问题,来自 http://en.wikipedia.org/wiki/P_versus_NP_problem 的摘录如下: “实质上,问题P = NP?问:假设可以快速验证对一个是或否的问题的肯定答案。那么,答案本身能否也被快速计算出来?”
我想知道,验证答案的速度与生成解决方案的速度有何关系?
这可能与编程有关,也可能与之无关。
人们关心 NP 问题是因为我们希望能够快速解决它们,但迄今为止我们还没有找到快速解决它们的方法。我们想知道是否有一种快速解决它们的方法,或者我们应该放弃尝试。
(Possibly.)
它们是否相关是Claypool基金会的“千年难题”之一,他们将向提供经过数年深入研究的适当证明的人提供一百万美元。
这些问题的类型比看起来更相关,因为另一个NP问题的定义是可以使用任意并行计算机有效地解决。
有一件事情真正引起人们的兴趣,那就是缺乏证据。类似的问题已经有证明了,但这个问题没有。这让人着迷,特别是数学家,因为一个证明可能会带来很多其他东西的见解。这显然适用于佩尔曼关于庞加莱猜想的证明,这也是Millenium难题之一。
另一个问题是这可能会产生的影响。目前,很少有人相信有一种有效的方法来解决NP完全问题,因此发现P!= NP对实际影响不大。发现一种有效的方法来解决NP完全问题将彻底改变计算机科学。这将使许多事情更容易,并通过使解密变得容易而摧毁我们所知道的加密技术。
P
是所有可以由确定性图灵机在多项式时间内计算的语言类。现代计算机非常像确定性图灵机,只是图灵机本质上具有无限的内存。这种区别通常在实际应用中被忽略。
NP
是所有可以由非确定性图灵机在多项式时间内计算的语言类。非确定性图灵机不对应于任何真实世界的设备。
计算复杂性的一个基本事实是,NP
等价于其验证问题在P
类中的语言类。事实上,NP
有时被定义为这个类;这两个定义是可互换的,而验证定义具有直接与现实世界中的确定性图灵机类似的计算机的相关性。
因此,NP
是可以在“真实”机器上进行多项式时间验证并且可以在非常相似的理论机器上进行多项式时间求解的问题类。因此,可解性和可验证性的问题是相互关联的。
P
和NP
是不等价的;也就是说,存在一些语言可以被非确定性图灵机在多项式时间内计算,但不能被确定性图灵机计算,或者等价地说,这些语言不能在确定性图灵机上以多项式时间解决,但它们的解可以被确定性图灵机在多项式时间内验证。虽然这里没有直接的关系。但是可能会有一种直觉感觉,验证答案比作为生成的一部分生成答案更容易,因为生成答案需要确保答案正确。因此,可以采用暴力方法尝试不同的解决方案,但这往往会导致超出P的指数复杂性,或者这就是我几年前在复杂度课程中记得的。
不,P≠NP。
答案是Co-NP-Asymmetric-Partially-Complete。
请到我的网站查看完整答案:
Singularitariantechnologies.wordpress.com
简单总结一下你的问题的答案,通常情况下是不行的,除非P=NP,因此共np-不对称部分不完整/完整的答案。
为了做到这一点,我使用Google.com作为数据库,可以在多项式时间内给我一个验证过的答案,然后我想看看是否可以根据最佳公理化约简来计算答案,其中包括指数项,本质上,即使我们知道验证过的答案是什么,但如果有两个以上的变量(在这种情况下是指数),答案也是无法计算的。
显然,这让黑客们没有其他选择,因为未来的加密算法将不会那么简单。此外,从公理上讲,多项式必须由多个术语组成,因此当变量>=3时,P=/=NP,当变量<=2时,P=NP,这只是一个实例。
请阅读我的网站或Google Drive上的完整文档,我还提供了一个电子表格链接,链接到我的singularitariantechnologies.wordpress.com上的工作。
这句话的意思是什么?未来将不会有黑帽子式的攻击,即使你试图通过模二公理化减少加密攻击,也无法在高级加密(复杂多项式加密,带有一些附加条件和花哨的功能,使破解密码或任何加密数据变得更加困难)中奏效。