%0 Journal Article
%T A Parallel Time-Memory-Processor Tradeoff O(25n/6) for Knapsack-Like NP-Complete Problems<br>背包类问题的并行O(25n/6)时间-空间-处理机折衷
%A LI Ken-Li
%A ZHAO Huan
%A LI Ren-Fa
%A LI Qing-Hua
%A <br>李肯立
%A 赵欢
%A 李仁发
%A 李庆华
%J 软件学报
%D 2007
%I 
%X A general-purpose parallel three-list six-table algorithm that can solve a number of knapsack-like NP-complete problems is developed in this paper. This kind of problems includes knapsack problem, exact satisfiability problem, set covering problem, etc. Running on an EREW PRAM model, The proposed parallel algorithm can find a solution of these problems of size n in O(27n/16) time, with O(213n/48) space and O(2n/8) processors, resulting in a time-space-processor tradeoff of O(25n/6). The performance analysis and comparisons show that it is both work and space efficient, and thus is an improved result over the past researches. Since it can break greater variables knapsack-based cryptosystems and watermark, the new algorithm has some cryptanalytic significance.
%K NP-complete problem
%K parallel algorithm
%K time-space-processor tradeoff
%K knapsack problem<br>NP完全问题
%K 并行算法
%K 时间-空间-处理机折衷
%K 背包问题
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=9B54FDB4F749DBE9&yid=A732AF04DDA03BB3&vid=13553B2D12F347E8&iid=B31275AF3241DB2D&sid=80428A5C4056DF37&eid=D103793C8B25974D&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=23