电子学报
電子學報
전자학보
ACTA ELECTRONICA SINICA
2011年
1期
128-132
,共5页
鲍皖苏%宋震%钟普查%付向群
鮑皖囌%宋震%鐘普查%付嚮群
포환소%송진%종보사%부향군
量子算法%子集和问题%计算复杂性%中间相遇
量子算法%子集和問題%計算複雜性%中間相遇
양자산법%자집화문제%계산복잡성%중간상우
子集和问题是NP完全问题,该问题是背包公钥的基础.现有最优的经典算法求解规模为n的子集和问题需要O(n2n/2)步运算.本文提出了基于时空折衷思想的量子中间相遇搜索算法,该算法可以在O(n2n/3)步求解规模为n的子集和问题,其存储复杂性为O(2n/3).由于NP完全问题可以在多项式时间内可相互归约,所以,在存储复杂性为O(2n/3)的条件下,量子中间相遇搜索算法使得NP完全问题的计算复杂性降为O(n2n/3).
子集和問題是NP完全問題,該問題是揹包公鑰的基礎.現有最優的經典算法求解規模為n的子集和問題需要O(n2n/2)步運算.本文提齣瞭基于時空摺衷思想的量子中間相遇搜索算法,該算法可以在O(n2n/3)步求解規模為n的子集和問題,其存儲複雜性為O(2n/3).由于NP完全問題可以在多項式時間內可相互歸約,所以,在存儲複雜性為O(2n/3)的條件下,量子中間相遇搜索算法使得NP完全問題的計算複雜性降為O(n2n/3).
자집화문제시NP완전문제,해문제시배포공약적기출.현유최우적경전산법구해규모위n적자집화문제수요O(n2n/2)보운산.본문제출료기우시공절충사상적양자중간상우수색산법,해산법가이재O(n2n/3)보구해규모위n적자집화문제,기존저복잡성위O(2n/3).유우NP완전문제가이재다항식시간내가상호귀약,소이,재존저복잡성위O(2n/3)적조건하,양자중간상우수색산법사득NP완전문제적계산복잡성강위O(n2n/3).
