| 子集和问题的量子中间相遇搜索算法 |
| |
| 引用本文： | 鲍皖苏,宋震,钟普查,付向群.子集和问题的量子中间相遇搜索算法[J].电子学报,2011,39(1):128-132. |
| |
| 作者姓名： | 鲍皖苏 宋震 钟普查 付向群 |
| |
| 作者单位： | 解放军信息工程大学电子技术学院;湖南省岳阳军分区; |
| |
| 摘 要： | 子集和问题是NP完全问题,该问题是背包公钥的基础.现有最优的经典算法求解规模为n的子集和问题需要O(n2n/2)步运算.本文提出了基于时空折衷思想的量子中间相遇搜索算法,该算法可以在O(n2n/3)步求解规模为n的子集和问题,其存储复杂性为O(2n/3).由于NP完全问题可以在多项式时间内可相互归约,所以,在存储复杂性...
|
| 关 键 词： | 量子算法 子集和问题 计算复杂性 中间相遇 |
| 收稿时间： | 2009-12-28 |
Quantum Mechanical Meet-in-the-middle Algorithm for Subset Sum Problem |
| |
| BAO Wan-su,SONG Zhen,ZHONG Pu-cha,FU Xiang-qun.Quantum Mechanical Meet-in-the-middle Algorithm for Subset Sum Problem[J].Acta Electronica Sinica,2011,39(1):128-132. |
| |
| Authors: | BAO Wan-su SONG Zhen ZHONG Pu-cha FU Xiang-qun |
| |
| Institution: | BAO Wan-su1,SONG Zhen1,ZHONG Pu-cha2,FU Xiang-qun1(1.Institute of Electronic Technology,The PLA Information Engineering University,Zhengzhou,Henan 450004,China,2.Yueyang Army Subarea of Hunan Province,Yueyang,Hunan 414000,China) |
| |
| Abstract: | Subset sum problem is one of the NP complete problems,which is the foundation of knapsack encryption schemes.Its computational complexity is O(n2exp(n/2)) in classical algorithms.We present the quantum mechanical meet-in-the-middle algorithm,which can solve the subset sum problem in O(n2exp(n/3)) with O(2exp(n/3)) memory cost,and O(2exp(n/2)) in quantum mechanical algorithm.The NP complete questions are minimized in O(n2exp(n/3)) under this algorithm because of their equivalence. |
| |
| Keywords: | quantum algorithm subset sum problem computational complexity meet-in-the-middle |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《电子学报》浏览原始摘要信息 |
| 点击此处可从《电子学报》下载免费的PDF全文 |
|
