On a communication complexity problem in combinatorial number theory

摘要

The original knapsack problem is well known to be NP-complete. In a multidimensional version, one have to decide whether a p ? N~k is in the sumset-sum of a set X ? N~k. In this paper, we are going to investigate a communication complexity problem related to this. We are also going to prove some results about the special case of the multidimensional knapsack problem, when the set X is in the form X = A i X···x A_k?N~k, where A_i is a so-called regular set for every i = 1, 2,..., k.