-
题名P vs. NP问题研究状态及其对密码学的意义
被引量：1
- 1
-
-
作者
王琪
姜新文
彭立宏
-
机构
国防科技大学计算机学院
-
出处
《计算技术与自动化》
2010年第3期66-72,共7页
-
文摘
介绍P vs.NP问题的研究状态以及P vs.NP问题的研究对于密码学的意义。主要内容包括关于证明P≠NP的主要研究方法和相关工作,关于证明P=NP的主要研究方法和相关工作,关于求解NP完全问题的相关方法,以及P vs.NP问题研究与密码学的关系。由于现代密码学建立在未知密钥情况下不存在有效的算法将明文消息从密文中提取出来的假定之上,因此安全加密算法存在的一个必要条件是P≠NP。如果P=NP,根据Cook的观点,现代密码体制将崩溃。依据P=NP的假定,给出一个可能的密码分析模型。
-
关键词
p
vs.
Np
密码学
Np完全
计算复杂性
MSp
-
Keywords
p vs.np
cryptology
Np-complete
computational complexity
MSp
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名时间旅行的量子门
- 2
-
-
作者
王粲
陆朝阳
陈明城
-
机构
中国科学技术大学近代物理系
中国科学技术大学
-
出处
《物理学报》
SCIE
EI
CSCD
北大核心
2024年第2期89-92,共4页
-
文摘
量子计算可以解决经典计算难于求解的问题,在物理原理允许范围内扩大了可有效计算的问题范围,对经典计算的扩展丘奇图灵论题提出了挑战.这里我们讨论一个有趣的问题:通过突破物理原理限制来实现更强大的计算机,进一步扩展量子计算机的能力.我们考虑一种全新的操纵能力,让量子计算可以实现时间穿梭旅行的量子控制门.这是量子门线路图形语言的一个符合直觉的扩展,作为例子,我们展示了一个可以有效求解SAT难题的扩展量子算法.我们的结果有助于更深刻地理解计算和物理原理之间的关系.
-
关键词
扩展丘奇图灵论题
时间旅行
闭合类时曲线
量子计算机
p与Np问题
-
Keywords
extended Church-Turing thesis
time travel
closed time-like curves
quantum computer
p vs.np problem
-
分类号
O413
[理学—理论物理]
TP38
[自动化与计算机技术—计算机系统结构]
-
