背包类问题的并行O(2^(5n/6))时间-空间-处理机折衷(英文)

作     者：李肯立 赵欢 李仁发 李庆华 LI Ken-Li;ZHAO Huan;LI Ren-Fa;LI Qing-Hua

作者机构：湖南大学计算机与通信学院湖南长沙410082 华中科技大学计算机学院湖北武汉430074 

基　　金：国家自然科学基金No.60603053 国家教育部重点基金No.105128 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2007年第18卷第6期

页      码：1319-1327页

摘      要：将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.

主 题 词：NP完全问题 并行算法 时间-空间-处理机折衷 背包问题 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.1360/jos181319

馆 藏 号：203147595...