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 \in ℕ^{k}$ is in the sumset-sum of a set $X \subseteq ℕ^{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_{1} \times \dots \times A_{k} \subseteq ℕ^{k}$ , where $A_{i}$ is a so-called regular set for every $i = 1, 2, \dots, k$ .

PDF Access Denied

We have not been able to recognize your IP address 3.133.112.73 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 40.00:

Keywords

subset sums, communication complexity, matching in bipartite graph

Mathematical Subject Classification

Primary: 11B30, 11B39, 11B75

Milestones

Received: 27 July 2021

Revised: 21 October 2021

Accepted: 7 November 2021

Published: 17 January 2022

Authors

Bence Bakos
Institute of Mathematics Eötvös University Budapest Hungary

Norbert Hegyvári
Institute of Mathematics Eötvös University Budapest Hungary	Alfréd Rényi Institute of Mathematics Budapest Hungary

Máté Pálfy
Institute of Mathematics Eötvös University Budapest Hungary

Vol. 10, No. 4, 2021

Bence Bakos, Norbert Hegyvári and Máté Pálfy

Abstract

PDF Access Denied

Keywords

Mathematical Subject Classification

Milestones

Authors