回答情况：
提问时间：
问题标签：
如果是P = NP，为什么P = NP也等于NP-Complete假设P != NP，在NP中存在问题，而不是在NP - Complete中。当P = NP时，所有NP问题现在实际上都是P。
NP - Complete中
浏览 0修改于2014-12-11得票数 0
4回答
正如大多数人知道的那样，P= NP是未经证实的，而且似乎不太可能是真的。证明将证明P <= NP和NP <= P，尽管其中只有一个是困难的。
根据定义，p <= NP几乎是真的。事实上，这是我唯一知道如何表述P <= NP的方法。这是很直观的。你如何证明P <= NP呢？
浏览 1提问于2010-04-15得票数 6
回答已采纳
9回答
关于P NP问题，摘自：“本质上，问题P= NP?问:假设一个是或否问题的yes答案可以快速验证。那么，答案本身也可以快速计算出来吗？”
我想知道，验证答案的速度与生成解决方案的速度有什么关系？
浏览 0修改于2010-08-12得票数 10
回答已采纳
1回答
该站点包含各种单向函数的讨论及其与P和NP的关系.\mid~ x'\le x \text{ and } f(x)=y \}
，其中f:\Sigma^*\to\Sigma^*是单向函数，x'\le x是前缀关系.现在的一个核心观点是，这种语言L包含在NP
浏览 0提问于2018-12-17得票数 5
回答已采纳
2回答
我最近听到一些人说，如果P= NP这一事实得到证实，大多数(全部？)目前被认为像RSA那样安全的密码算法在安全系统中是不可用的。我的问题是：2.如果没有，我们能做些什么来保证至少同等数量的安全(使用更大的密钥长度？
浏览 0修改于2013-06-27得票数 7
回答已采纳
当我想到这一点时，我意识到“密码恢复”问题是NP问题的一个很好的例子。如果你知道密码，就很容易在多项式时间内验证它。但是如果你不知道密码，你必须搜索整个可能的解决方案空间，这可能会花费指数级的时间。现在我的问题是:这不是证明了P != NP吗，因为“密码恢复”是NP的一个元素，可以证明它需要多项式时间才能运行？
浏览 2修改于2010-03-12得票数 9
回答已采纳
2回答
让我们假设最坏的情况:构造性证明的P=NP。因此，3-SAT和直接多项式攻击AES和所有其他标准模型对称密码.
除了使用欧洲央行和每个密钥发送一个块之外，我们如何构建一个需要严重攻击才能打破的东西？我意识到在这个P=NP世界结束是不可能的。我还知道这个旧职位描述了为什么P=?NP是一个糟糕的易碎模型的很好的原因。
浏览 0修改于2019-05-20得票数 3
根据这，单向函数的存在证明了P-≠NP.这有什么证据？
证明这一点的一种方法是，如果P= NP，那么任何函数都很容易反转。P和NP是关于决策问题的，而不是计算问题。
浏览 0提问于2016-09-10得票数 11
回答已采纳
我知道P=NP到目前为止还没有解决，但是有谁能告诉我以下几点:目前最有希望解决这个问题的数学/计算机科学方法是什么？或者说，到目前为止，甚至没有任何这样的方法被认为是有潜在帮助的？
浏览 0修改于2013-12-08得票数 8
回答已采纳
1回答
从维基百科引述的P vs NP问题，关于算法的时间复杂性，“……询问是否每个其解决方案可以被计算机快速验证的问题也可以被计算机快速解决。”
浏览 0提问于2012-10-08得票数 7
回答已采纳
1回答
最近有什么问题(也可以随意添加“旧”问题)被认为是NP，然后有人想出了一个多项式的解决方案吗？我认为，研究这些案例将有助于在实践竞争性编程的同时，发展解决关键问题的诀窍。
浏览 0提问于2018-06-12得票数 0
回答已采纳
如果我们假设发现了P=NP，那么安全措施需要如何改变呢？
我想知道受影响的主要安全措施，以及需要如何改变这些措施。为了便于论证，我们可以假设密码可以在时间O(n^4)中被黑。
浏览 0提问于2012-03-16得票数 21
有人能链接我一个证明或写一个指出解决2SAT#P算法可以解决任何NP问题的证明吗，因为上面说2SAT#P解决了PvsNP？
浏览 0修改于2020-07-17得票数 0
1回答
鉴于Shor算法可以在量子计算机( BQP )上求解多项式时间内的因式分解，如果我们证明BQP和经典计算机上的BQP是相同的，那么分解(这是NP问题)难道不是P != NP的反例吗？换句话说，如果这个陈述是真的，那么P != NP不是真的吗，因为我们可以在P时间内解决一个NP问题(因式分解)？
浏览 2提问于2022-09-22得票数 0
回答已采纳
我知道，我知道-“如果P=NP”是一个非常大，高影响的假设。我的意思是，显然RSA (以及类似的混淆方法)很可能变得完全不相关--或者他们会吗？相对于指数时间而言，在多组分中可解是一个重大的打击，但它们是否能利用如此大的公钥/私钥(如果P=NP，那么更有效的素数定位器似乎很有可能)，以致于破解它们仍然“困难”吗？
这些大多只是讨论的要点。就原始问题而言:什么密码学方法最终不依赖于P!=NP？
浏览 0提问于2014-03-15得票数 0
比如imp中的P变成了not中的NP？NP是prolog中P的否定吗？非常感谢。
浏览 2修改于2014-02-04得票数 0
回答已采纳
1回答
假设您有一个程序P和n语句。它通过一个状态序列(变量值) s (其中s是一个向量)并生成输出x。我们可以提出两个问题：
A.对于一个程序P，该程序使用n语句生成x (可能通过s)，它可以证明没有q<code>E 238</code>可以在<code>e 139</code>m<code>E 240</代码>语句中找到有一个简单的解决方案:对于任何P，运行P并记录x。现在编写一个程
浏览 1修改于2012-09-01得票数 1
回答已采纳
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号