On the distribution of subset sums of certain sets in ℤ²_p

2023/04/04 by Hegyvári, Norbert
#Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2304.01777

Abstract

A given subset A of natural numbers is said to be complete if every element of ℕ 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× B is not necessarily complete in ℕ². In this paper we consider a modular version of this problem, motivated by the communication complexity problem of [2].

Related

• On a Communication Complexity problem in Combinatorial Number Theory
• On the structures of subset sums in higher dimension
• Knapsack Problems in Groups
• Modular Subset Sum, Dynamic Strings, and Zero-Sum Sets
• On Strong NP-Completeness of Rational Problems