Abstract:
We show that it is not possible to speed-up the Knapsack
problem efficiently in the parallel algebraic decision tree model. More
specifically, we prove that any parallel algorithm in the fixed degree
algebraic decision tree model that solves the decision version of the
Knapsack problem requires 
rounds even by using
processors. We extend the result to the PRAM model without
bit-operations. These results are consistent with Mulmuley's recent result on
the separation of the strongly-polynomial class and the corresponding NC
class in the arithmetic PRAM model
Available as PostScript, PDF, DVI.