An alternative to Ben-Or's lower bound for the knapsack problem complexity

Abstract

In this paper, we study the algebraic complexity of the knapsack problem in the form a(T)x = 1, x is an element of Z(n) (KPR), and its Boolean version a(T)x = 1, x is an element of {0, 1}(n) (0/1-KPR), in the framework of a real number model of computation. We show that no algorithm for these problems can achieve a time bound o(n log n) (.) f(a(1),..., a(n)), where f is any arbitrary continuous function of n variables. This result complements the well-known Ben-Or's lower bound Omega(n(2)) [1]. (C) 2002 Elsevier Science Ltd. All rights reserved.