背包类问题的并行O(25n/6)时间-空间-处理机折衷

摘要：

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

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

所属期刊栏目：18

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金60603053;教育部科学技术研究重点项目105128

在线出版日期：2007-07-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1319-1327