On the distribution of subset sums of certain sets in ${\mathbb{Z}}_p^2$

Abstract

A given subset $A$ of natural numbers is said to be complete if every element of $\mathbb{N}$ is the sum of distinct terms taken from $A$. This topic is strongly connected to the knapsack problem which is known to be NP complete. Interestingly if $A$ and $B$ are complete sequences then $A\times B$ is not necessarily complete in ${\mathbb{N}}^2$. In this paper we consider a modular version of this problem, motivated by the communication complexity problem of [2].

7 pages comments are welcome