首页 | 本学科首页   官方微博 | 高级检索  
文章检索
  按 检索   检索词:      
出版年份:   被引次数:   他引次数: 提示:输入*表示无穷大
  收费全文   1篇
  完全免费   2篇
  自动化技术   3篇
  2014年   1篇
  2001年   2篇
排序方式: 共有3条查询结果,搜索用时 31 毫秒
1
1.
赵运磊  朱洪 《软件学报》2001,12(5):656-658
1975年,Lander证明在P≠NP假设下存在一个语言属于NP-NPC-P(NPI).但Lander给出语言并不是一个自然的语言因在该语言的构造中需运行所有多项式时间的图灵机.迄今为止,还没有自然的语言被证明在P≠NP假设下属于NPI,并且在P≠NP假设下寻找一个属于NPI的自然语言是一个重要的未解决问题.作者部分解决了此长期未解决的问题.定义了2+f(m)-HAST模型.基于该模型,给出了在P≠NP假设下NP-NPC-P中自然问题的一个候选者.已证明在P≠NP假设下它不属于NPC并且在更强但合理的假设下它的确属于NPI.  相似文献
2.
NPPP          下载免费PDF全文
赵运磊  朱洪  赵一鸣 《软件学报》2001,12(7):967-970
主要目的是研究NP与PP的关系。引入了一个NP的等价的随机定义。基于此等价定义,定义了另一个随机复杂性类:SUPER-NP。虽然SUPER-NP与NP非常接近,但令人吃惊的是发现了PP包含于SUPER-NP,从而NP包含于PP包含于SUPER-NP。考虑到NP=PCP(log,O(1))以及NP和SUPER-NP的相似性,也希望能通过证明SUPER-NP包含于PCP(log^2,O(1))来解决PP包含于PCP(log^2,O(1))的猜想。  相似文献
3.
Schnorr身份认证方案是密码学中的经典方案,可以推广到很多其他数学问题(如离散对数问题)上,从而构造出在标准模式中安全的身份认证方案,并且可以通过Fiat-Shamir转换工具,将其转换为在随机谕示模式中安全的数字签名方案。但将上述转换方法用于基于格的密码学中时会出现一些特殊现象(如方案中止现象)。为此,通过矩阵表示方法分析Schnorr方案的构造方法,得出其构造方法成立的充要条件,从而使其可在更大范围内构造出安全的类Schnorr方案。根据类Schnorr方案,分析基于格的身份认证方案中的方案中止现象,并通过数学方法证明,对于某些身份认证方案(如∑-身份认证方案),其中的方案中止现象不可避免,该结论为深入研究基于格的密码学提供了参考依据。  相似文献
1
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号