On Parallel Computation for the Knapsack Problem
Andrew Chi-Chih Yao · Journal of the ACM · 1982
The complexity of solwng the knapsack problem with n input real numbers on a parallel computer wRh real arithmeUc and branching operations is considered A trine-processor trade-off constraint ts derived; m particular, it ts shown that an exponential number of processors have to be used if the problem is to be solved m time t _< ~n/2.