0
$\begingroup$

I have a grocery dotted list of pairs which are missing items that I need and I don't have any of them, so I am going to the supermarket.

Each pair in the dotted list is the name of the missing item that I need and a natural number which is the quantity/amount i.e. how many of this item I need.

I am in the supermarket now and I see an array of packages of items standing on shelf.

There are packages that don't contain items that I don't need and there are packages that contain items that I don't need.

I have enough money to buy all the packages, but if I will do this then I will get items that I don't need, so I don't want to do this.

Surely that I won't buy any package that contains an item that I don't need, but note that I don't want to have too many of any item that I need.

I can peek inside each package to see what items it contains and how many of that item it contains.

I cannot buy partial package, i.e. I cannot for each package decide which items from the package I buy and which I don't buy.

My only choice for each package is either buy the package and get all the items inside or don't buy the package and get nothing from the items that this package contains.

I want to know if this is possible to buy the packages so I get all what I need exactly as written in my grocery dotted list without having superfluous items that I don't need.

I will bring my mobile phone to the supermarket and once I can peek inside the packages I will run the application that will solve my problem.

I am programmer and I can program this application for my mobile phone with no problem but I want to use a polynomial time algorithm that solves my problem, because I am not going to wait hours, days, months and years until my phone will return me the answer.

But to know if there is polynomial algorithm or not I need to know first if my problem is NP-Hard or NP-Intermediate that polynomial solution is unknown.

Indeed my problem is decision, because I need to decide which packages I buy and which I don't buy and if I have a solution I can verify it in polynomial time, so my problem is indeed in $\mathbb{NP}$, but I don't know if it is in $\mathbb{P}$.

Do you know?

EDIT:

Mathematically my problem is show either:

$A\subset\mathbb{MULTISETS} \land B\in\mathbb{MULTISETS}\vdash\exists C: C \subseteq A \land \displaystyle \biguplus_{D \in C}D=B$

OR

$A\subset\mathbb{MULTISETS} \land B\in\mathbb{MULTISETS}\vdash\nexists C: C\subseteq A \land \displaystyle \biguplus_{D \in C}D=B$

Improve this question
$\endgroup$
13
  • 5
    $\begingroup$ You could write this whole question in about ten lines. I strongly suggest you do so, because people are much more likely to answer questions that don't make them do a whole pile of unnecessary reading. $\endgroup$
    – David Richerby
    Aug 30, 2017 at 20:03
  • 1
    $\begingroup$ Using multisets definition, I think. In multiset number of same elements is counted. $\endgroup$
    – rus9384
    Aug 30, 2017 at 20:14
  • 1
    $\begingroup$ You have a bunch of multisets $A_1,A_2,...,A_k$ and a multiset $B$. Now you want to know if there even is such a combination $A_{p_1}\cup A_{p_2}\cup...\cup A_{p_m} = B;~|p|\leq k$. And yes, $\forall i\forall (j\neq i):p_i\neq p_j$. $\endgroup$
    – rus9384
    Aug 30, 2017 at 20:26
  • 1
    $\begingroup$ That's not a solution, that's short description of problem. Of course there is exponential solution, but I don't know if this is NP-complete. $\endgroup$
    – rus9384
    Aug 30, 2017 at 20:31
  • 2
    $\begingroup$ Here's your whole question in a comment, with 9 characters to spare. "I wish to buy nonnegative integer quantities $q_1, \dots, q_n$ of items $1, \dots, n$, respectively (some of the $q_i$ may be zero). Unfortunately, the shop doesn't sell items individually, but only sells pre-packed boxes of items. Each box contains some number (possibly zero) of each item. What is the complexity of determining whether some combination of the boxes contain between them exactly $q_i$ of item $i$ for each $i$? (It is not possible to buy a part of a box: I must either buy the whole box or not buy it.)" $\endgroup$
    – David Richerby
    Aug 30, 2017 at 22:09

1 Answer 1

Reset to default
2
$\begingroup$

Your problem is NP-complete.

It is a multidimensional generalization of the subset sum problem. The input to subset sum is a list of integers $a_1, \dots, a_n$ and a target $t$. The question is whether there's some sublist of the integers whose total is $t$. This corresponds to the case where your shopping list is just "$t$ apples" and each package on the shelf contains some number of apples.

Having multiple products for sale in the shop certainly can't make the problem any easier. But it doesn't get any harder, either: it's still in NP because, as you've observed, if somebody tells you "buy this set of packages", you can easily check in polynomial time that this gives you exactly what you want.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Oh no! I failed to prove that integer factorization is np-hard! $\endgroup$
    – Farewell Stack Exchange
    Aug 30, 2017 at 22:28
  • 1
    $\begingroup$ Don't worry. All the best computer scientiest have failed to prove that! :-) $\endgroup$
    – David Richerby
    Aug 30, 2017 at 22:33
  • 1
    $\begingroup$ At least I tried and I was close :-) I am going to sign to physics degree and once I am graduated I will try to answer the BQP vs NP question and maybe find out that $\mathbb{NP}\nsubseteq\mathbb{BQP}$ $\endgroup$
    – Farewell Stack Exchange
    Aug 30, 2017 at 22:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.