%0 Journal Article
%T 背包类问题的并行o(25n/6)时间-空间-处理机折衷
%A 李肯立？
%A 赵欢？
%A 李仁发？
%A 李庆华？
%J 软件学报
%P 1319-1327
%D 2007
%X 将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类np完全问题的并行三表六子表算法.基于erew-pram模型,该算法可使用o(2n/8)的处理机在o(27n/16)的时间和o(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为o(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.
%K np完全问题
%K 并行算法
%K 时间-空间-处理机折衷
%K 背包问题
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=20070607&flag=1