<p>As the problem is phrased there is no dependency between the customers so it should be easy to solve: check your constraint for every customer independently. This is clearly fast (linear in the number of purchased pieces times number of customers).</p>

CC BY-SA 2.5
2010-11-08T11:48:20.977Z
It doesn't seem like the OP forbids customers interested in the same items, so there could be a dependency in the sense that we might satisfy more customers by excluding some customers who, for instance, want to buy the whole stock available for a given item.
Anthony Labarre
CC BY-SA 2.5
2010-11-08T12:06:31.250Z
The dependency between customers is that they may want to buy the same good. Since there are at most X pieces of each good, if more than X customers want the same good, some of them are satisfied and others not.
user2094
CC BY-SA 2.5
2010-11-08T13:38:57.310Z
This is not how I understood the meaning of X. As stated above, each good is a composite of X pieces with different weights. There is no statement about the number of available goods/pieces. Please clarify the question.
Raphael
CC BY-SA 2.5
2010-11-08T10:38:17.007Z
2010-11-08T10:38:17.007Z
Raphael
<p>(I have posted this answer as a comment on the question, but I am reposting it with a little more detail.)</p>

<p>This problem is NP-hard as follows.</p>

<p>As is usual in a proof of NP-hardness, suppose that a natural number <i>K</i> is also given as part of input, and consider the yes/no problem of deciding whether at least <i>K</i> customers are satisfied.  Then this problem is NP-complete, even if it is restricted to the case where <i>X</i>=1, <i>m</i>=3<i>K</i> and each customer wants to buy exactly three goods.  (Note that if <i>X</i>=1, the value of <i>Y</i> is irrelevant as long as <i>Y</i>&gt;0.)  In this case, the problem is equivalent to the NP-complete problem called Exact Cover by 3-Sets.</p>

<p>See <a href="http://en.wikipedia.org/wiki/Computers_and_Intractability%3a_A_Guide_to_the_Theory_of_NP-Completeness" rel="nofollow">Garey and Johnson</a> for more on complexity theory and NP-completeness, including the definition of the Exact Cover by 3-Sets and the proof of its NP-completeness.</p>

CC BY-SA 2.5
2010-11-09T11:33:47.633Z
2010-11-09T11:43:04.100Z
2010-11-09T11:43:04.100Z
Tsuyoshi Ito
<p>I'm not expert on complexity theory and combinatorial optimization.
I want to know if the following problem (or similar) is known in the scientific literature, and if you think it is NP-complete.
Thank you in advance for your help.</p>

<p><strong>Input:</strong></p>

<p>Two parameters X and Y, which can be equal.<br>
n customers C1, C2, ... Cn<br>
m types of goods M1, M2 ... Mm</p>

<p>There are X pieces available for each good Mi: a piece of 1kg, another piece of 2kg, ...., a piece of X kg.<br>
Every customer wants to buy a certain number of goods. For example, the client C1 may be interested in buying goods M1, M4, M8 and M9.
A customer is <strong>satisfied</strong> if he can find all the goods he wants to buy. In addition, the weights of the parts he was able to purchase must satisfy a constraint that I'll explain below.</p>

<p><strong>Output:</strong>
How many customers can be satisfied?</p>

<p>The constraint on the weights is as follows:
Take for example the client C1 who is interested in buying goods M1, M4, M8 and M9. Assume that C1 was able to purchase all four goods. Let P1, P2, P3, P4 be the weights of the pieces he was able to buy.
C1 is satisfied if $\sum_i  P_i -1 &lt;Y$.  </p>

<p>Edit: Note that the limit Y is common for all customers. The intuition behind the constraint is that we want to limit the number of pieces whose weight is not equal to 1kg.</p>

CC BY-SA 2.5
2010-11-08T14:04:01.150Z
@Tsuyoshi: We certainly don't want homework problems at this level. I'm in favor of allowing other problems at this level, because I think we want to reach out to other areas of computer science, and they aren't necessarily going to know the difference between an easy problem and a hard, interesting problem. On the other hand, we could require people from other areas of CS to tell us why they're interested in the problem; this would screen out homework problems.
Peter Shor 
CC BY-SA 2.5
2010-11-08T14:15:50.597Z
@Peter: Thanks, and I agree.  I wrote the answer because I assumed that this was not a homework problem (I hope that my assumption was correct).  Next time I will remember to ask motivations.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-08T15:21:48.527Z
just my .02, but this didn't sound like a homework problem to me.
Suresh Venkat
CC BY-SA 2.5
2010-11-08T17:24:11.273Z
I can assure the sceptics that this is not a homework question. Alone, I would have spent weeks and weeks trying to solve it. Thanks to the help of Tsuyoshi, I can concentrate on other things that are in the core of my work. Thanks.
user2094
CC BY-SA 2.5
2010-11-08T17:52:16.050Z
@Tsuyoshi: you should put your comment as an answer!
arnab
CC BY-SA 2.5
2010-11-08T18:12:11.803Z
@user2094, if you're comfortable giving us more information about yourself/the application you're interested in, this could provide a good example of how this site helps with outreach (per Peter's comment)
Suresh Venkat
CC BY-SA 2.5
2010-11-08T22:42:51.633Z
@user2094, I actually never thought this was a homework problem (homework problems tend to be somewhat more crisply formulated, and have fewer constraints that are extraneous to the solution). And indeed, Tsuyoshi's suggestion of Exact Cover by 3-Sets seems the best problem to use for reduction. My comment was to suggest to leave this question open, since I think we should only close easy homework problems.
Peter Shor 
CC BY-SA 2.5
2010-11-09T11:34:13.843Z
@arnab: Done. -
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-10T07:00:33.597Z
Why even close those sorts of questions? It seems like the best way to draw in more people to theoretical CS. Taking a hardline "no easy problems" position is more likely to just drive a good chunk of userbase away. To a lot of people, ideas like these can be a dark art and having somewhere to go can be most helpful. If you only want "hard interesting questions" you're going to lose a lot of people.
Xorlev
CC BY-SA 2.5
2010-11-10T10:39:46.870Z
I agree with @Xorlev, there is currently no place to publish NP-hardness results as they are now rather routine.  This site already has several examples of new reductions, and it seems a good use of the site: it is a nice win-win situation, a match between something often rather easy to a complexity theorist, and something rather hard (but potentially valuable) to someone who is not.
András Salamon
CC BY-SA 2.5
2010-11-10T12:55:02.823Z
Ok, ok, I was wrong even to suggest the possibility that the question might not be suitable on this website!  (But to be honest, I am personally satisfied because I have learned which questions should be allowed and should not be allowed from the comments on this question.)  Let me clarify two things: (1) No one has voted to close this question.  (2) No one has stated that he/she thought that this question was a homework.  On the contrary, several people (including me) stated that this question did _not_ look like a homework, which is consistent with the asker’s comment.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-10T15:57:19.317Z
@Tusyoshi: I think we're still working out which problems should be allowed and which shouldn't (and remarkably, I think we're coming to a reasonable consensus). Your suggestion that it might not be suitable certainly contributed the process, so it was actually quite useful.
Peter Shor 
CC BY-SA 2.5
2010-11-08T10:21:56.303Z
The constraint \sum (p_i -1) < Y is a little odd. Why the "-1" ? and is it the same Y for all customers ?
Suresh Venkat
CC BY-SA 2.5
2010-11-08T10:24:03.170Z
the (-1) is to limit the number of pieces whose weight is greater than 1 kg, so the constraint favor the pieces of 1kg.
user2094
CC BY-SA 2.5
2010-11-08T10:27:44.850Z
Yes Y is common. I edited the question. thank you for your interest.
user2094
CC BY-SA 2.5
2010-11-08T12:40:36.123Z
I corrected some obvious errors in markup, but please make sure everything is shown as you intended.  [More on rereading your question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/328#328).
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-08T13:10:39.980Z
The problem is NP-hard because it contains the Exact Cover by 3-Sets as a special case (set X=1 and consider the case where every customer wants exactly three goods).  I am not sure if we want questions at this level.
Tsuyoshi Ito
<cc.complexity-theory><graph-theory><np-hardness><optimization>
Is the following problem NP-Hard?
user2094
# Is the following problem NP-Hard?

(Asked by: username_0 on 2010-11-08)

I'm not expert on complexity theory and combinatorial optimization.
I want to know if the following problem (or similar) is known in the scientific literature, and if you think it is NP-complete.
Thank you in advance for your help.

**Input:**

Two parameters X and Y, which can be equal.  
n customers C1, C2, ... Cn  
m types of goods M1, M2 ... Mm

There are X pieces available for each good Mi: a piece of 1kg, another piece of 2kg, ...., a piece of X kg.  
Every customer wants to buy a certain number of goods. For example, the client C1 may be interested in buying goods M1, M4, M8 and M9.
A customer is **satisfied** if he can find all the goods he wants to buy. In addition, the weights of the parts he was able to purchase must satisfy a constraint that I'll explain below.

**Output:**
How many customers can be satisfied?

The constraint on the weights is as follows:
Take for example the client C1 who is interested in buying goods M1, M4, M8 and M9. Assume that C1 was able to purchase all four goods. Let P1, P2, P3, P4 be the weights of the pieces he was able to buy.
C1 is satisfied if $\sum\_i P\_i -1 

Edit: Note that the limit Y is common for all customers. The intuition behind the constraint is that we want to limit the number of pieces whose weight is not equal to 1kg.

**Tags:** cc.complexity-theory, graph-theory, np-hardness, optimization
> **Comments:**
> **username_3**: The constraint \sum (p_i -1) < Y is a little odd. Why the "-1" ? and is it the same Y for all customers ?  
> **username_0**: the (-1) is to limit the number of pieces whose weight is greater than 1 kg, so the constraint favor the pieces of 1kg.  
> **username_0**: Yes Y is common. I edited the question. thank you for your interest.  
> **username_2**: I corrected some obvious errors in markup, but please make sure everything is shown as you intended.  [More on rereading your question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/328#328).  
> **username_2**: The problem is NP-hard because it contains the Exact Cover by 3-Sets as a special case (set X=1 and consider the case where every customer wants exactly three goods).  I am not sure if we want questions at this level.  
> **username_1**: @Tsuyoshi: We certainly don't want homework problems at this level. I'm in favor of allowing other problems at this level, because I think we want to reach out to other areas of computer science, and they aren't necessarily going to know the difference between an easy problem and a hard, interesting problem. On the other hand, we could require people from other areas of CS to tell us why they're interested in the problem; this would screen out homework problems.  
> **username_2**: @Peter: Thanks, and I agree.  I wrote the answer because I assumed that this was not a homework problem (I hope that my assumption was correct).  Next time I will remember to ask motivations.  
> **username_3**: just my .02, but this didn't sound like a homework problem to me.  
> **username_0**: I can assure the sceptics that this is not a homework question. Alone, I would have spent weeks and weeks trying to solve it. Thanks to the help of Tsuyoshi, I can concentrate on other things that are in the core of my work. Thanks.  
> **username_4**: @Tsuyoshi: you should put your comment as an answer!  
> **username_3**: @user2094, if you're comfortable giving us more information about yourself/the application you're interested in, this could provide a good example of how this site helps with outreach (per Peter's comment)  
> **username_1**: @user2094, I actually never thought this was a homework problem (homework problems tend to be somewhat more crisply formulated, and have fewer constraints that are extraneous to the solution). And indeed, Tsuyoshi's suggestion of Exact Cover by 3-Sets seems the best problem to use for reduction. My comment was to suggest to leave this question open, since I think we should only close easy homework problems.  
> **username_2**: @arnab: Done. -  
> **username_5**: Why even close those sorts of questions? It seems like the best way to draw in more people to theoretical CS. Taking a hardline "no easy problems" position is more likely to just drive a good chunk of userbase away. To a lot of people, ideas like these can be a dark art and having somewhere to go can be most helpful. If you only want "hard interesting questions" you're going to lose a lot of people.  
> **username_6**: I agree with @Xorlev, there is currently no place to publish NP-hardness results as they are now rather routine.  This site already has several examples of new reductions, and it seems a good use of the site: it is a nice win-win situation, a match between something often rather easy to a complexity theorist, and something rather hard (but potentially valuable) to someone who is not.  
> **username_2**: Ok, ok, I was wrong even to suggest the possibility that the question might not be suitable on this website!  (But to be honest, I am personally satisfied because I have learned which questions should be allowed and should not be allowed from the comments on this question.)  Let me clarify two things: (1) No one has voted to close this question.  (2) No one has stated that he/she thought that this question was a homework.  On the contrary, several people (including me) stated that this question did _not_ look like a homework, which is consistent with the asker’s comment.  
> **username_1**: @Tusyoshi: I think we're still working out which problems should be allowed and which shouldn't (and remarkably, I think we're coming to a reasonable consensus). Your suggestion that it might not be suitable certainly contributed the process, so it was actually quite useful.  

---

## 2 answers

### Answer by username_2 on 2010-11-09. Score: 16 | Accepted answer

(I have posted this answer as a comment on the question, but I am reposting it with a little more detail.)

This problem is NP-hard as follows.

As is usual in a proof of NP-hardness, suppose that a natural number *K* is also given as part of input, and consider the yes/no problem of deciding whether at least *K* customers are satisfied. Then this problem is NP-complete, even if it is restricted to the case where *X*=1, *m*=3*K* and each customer wants to buy exactly three goods. (Note that if *X*=1, the value of *Y* is irrelevant as long as *Y*>0.) In this case, the problem is equivalent to the NP-complete problem called Exact Cover by 3-Sets.

See [Garey and Johnson](http://en.wikipedia.org/wiki/Computers_and_Intractability%3a_A_Guide_to_the_Theory_of_NP-Completeness) for more on complexity theory and NP-completeness, including the definition of the Exact Cover by 3-Sets and the proof of its NP-completeness.


---

### Answer by username_7 on 2010-11-08. Score: -3

As the problem is phrased there is no dependency between the customers so it should be easy to solve: check your constraint for every customer independently. This is clearly fast (linear in the number of purchased pieces times number of customers).

> **Comments:**
> **username_8**: It doesn't seem like the OP forbids customers interested in the same items, so there could be a dependency in the sense that we might satisfy more customers by excluding some customers who, for instance, want to buy the whole stock available for a given item.  
> **username_0**: The dependency between customers is that they may want to buy the same good. Since there are at most X pieces of each good, if more than X customers want the same good, some of them are satisfied and others not.  
> **username_7**: This is not how I understood the meaning of X. As stated above, each good is a composite of X pieces with different weights. There is no statement about the number of available goods/pieces. Please clarify the question.  

---

