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

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