3
$\begingroup$

Given a set of vectors $V = \{v_1, v_2, \cdots, v_n\}, v_i \in \mathbb{Z}^2$.

Given a query $\vec{C} = (c_1, c_2), c_i \in \mathbb{Z}$, how can one quickly verify whether if there exists a subset $ S\subseteq V$, such that $\sum_{v \in S}v == \vec{C}$ ?

And I have a constraint on query $\vec{C}$ which only two forms are allowed $(0, \sum_{v\in V} v[1])$ or $=(\sum_{v\in V} v[0], 0)$

A brute force approach can be treating every dimension independently first and then somehow figure out a way to intersect both feasible regions.

$\endgroup$
6
  • 1
    $\begingroup$ Your problem is at least as hard as subset sum (because the second coordinates could be all zero). Also you could encode your vectors $(x_1,x_2)$ as integers $x_1 + Mx_2$, with $M$ big enough. Then just solve as an ordinary subset sum problem. Now subset sum is NP-complete so finding a quick way may be nontrivial. $\endgroup$ Mar 23, 2021 at 2:42
  • $\begingroup$ right, but I'm wondering if there is any better way to solve it so that it's not NP-complete. $\endgroup$
    – yupbank
    Mar 23, 2021 at 2:44
  • 1
    $\begingroup$ Do you have any extra constraints e.g. on the values? Otherwise your problem is NP-complete because it contains SUBSET SUM as a special case (with second coordinates zero), and that is already NP-complete. $\endgroup$ Mar 23, 2021 at 2:46
  • 2
    $\begingroup$ can you please put all the constraints in the question, instead of having people ekeing them out of you in Q&A fashion. $\endgroup$
    – kodlu
    Mar 23, 2021 at 5:30
  • 2
    $\begingroup$ The new constraint looks interesting, but the problem still contains the one-dimensional subset sum. $\endgroup$ Mar 23, 2021 at 6:50

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.