On a Communication Complexity problem in Combinatorial Number Theory

Autor:	Bakos, Bence, Hegyvári, Norbert, Pálfy, Máté
Rok vydání:	2021
Předmět:	Computer Science - Discrete Mathematics Mathematics - Combinatorics
Druh dokumentu:	Working Paper
Popis:	The original knapsack problem is well known to be NP-complete. In a multidimensional version one have to decide whether a $p\in \N^k$ is in a sumset-sum of a set $X \subseteq \N^k$ or not. In this paper we are going to investigate a communication complexity problem related to this.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2103.08174 Zobrazit plný text záznamu View this record from Arxiv