Skip to main content
Theoretical Computer Science

Return to Question

added a tag
Link
Mohammad Al-Turkistany
Mohammad Al-Turkistany
  • 21.1k
  • 5
  • 66
  • 152
Tweeted twitter.com/#!/StackCSTheory/status/138985313761640448
seeming typo
Source Link
Tsuyoshi Ito
Tsuyoshi Ito
  • 16.6k
  • 2
  • 56
  • 106

Given integers $a_1, \ldots, a_n, n \in \mathbb{N}$$a_1, \ldots, a_n, b \in \mathbb{N}$. What is the complexity of the following problem $$ \exists x_1, \ldots, x_n \in \mathbb{N} \text{ such that } a_1x_1 + \ldots a_nx_n = b? $$ I can't find this subset-sum variant in the literature.

Given integers $a_1, \ldots, a_n, n \in \mathbb{N}$. What is the complexity of the following problem $$ \exists x_1, \ldots, x_n \in \mathbb{N} \text{ such that } a_1x_1 + \ldots a_nx_n = b? $$ I can't find this subset-sum variant in the literature.

Given integers $a_1, \ldots, a_n, b \in \mathbb{N}$. What is the complexity of the following problem $$ \exists x_1, \ldots, x_n \in \mathbb{N} \text{ such that } a_1x_1 + \ldots a_nx_n = b? $$ I can't find this subset-sum variant in the literature.

Source Link
Paul
Paul
  • 61
  • 2

Complexity of a subset sum variant

Given integers $a_1, \ldots, a_n, n \in \mathbb{N}$. What is the complexity of the following problem $$ \exists x_1, \ldots, x_n \in \mathbb{N} \text{ such that } a_1x_1 + \ldots a_nx_n = b? $$ I can't find this subset-sum variant in the literature.