0
$\begingroup$

So I have a problem, I'm highly confident that it's NP-Hard, though I'm not really sure how I can convince my self this is the case?

Suppose I have different groups of people m in a list

M= {m1, m2}

and a list of food they can eat and the respective cost in dollars

Food = {f1:2, f2:3, f3:2}

you have buffet and can choose which food you can offer from the list, you can offer all the options or none. You will be paying for the food in hopes the tip will cover the cost.

each group will tip a certain amount if and only if all the option they like are available in the buffet, otherwise they tip 0.

Liked food = {(M1:f3: tip = 5), (M2:f1,f2: tip=10)}

profit = Tip - cost of food

f1 = 0 - 2 = -2

f2 = 0 - 3 = -3

f3 = 5 - 2 = 3

f1,f2 = 10 - 5 = 5

f1, f3 = 5 -5 = 0

f2,f3 = 5 - 5 =0

f1,f2,f3 = 15 - 7 = 8

Therefore to maximize profit you must purchase all the food and you will profit 8 dollars.

I believe that the question is NP-Hard, my prof says otherwise.

I already can clearly see there is no polynomial time verifier for this question and it's impossible to guarantee the solution is most optimal without trying the other all the other combos.

This means to show its NP-hard I'd have to do a reduction? Though I'm not really sure where to begin? Is my prof correct in saying its not NP-Hard?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You ask where to begin. See cs.stackexchange.com/q/11209/755, cs.stackexchange.com/q/1240/755, cs.stackexchange.com/q/9556/755 -- they will have some advice for where to begin, and some techniques you can study and learn. $\endgroup$
    – D.W. ♦
    Jun 28, 2015 at 4:13
  • $\begingroup$ "I already can clearly see there is no polynomial time verifier for this question and it's impossible to guarantee the solution is most optimal without trying the other all the other combos." This statement makes absolutely no sense. The question about there being a verifier is irrelevant since this is not a decision problem and if you wanted to show $NP$-hardness any question about a verifier is irrelevant. The second part would mean you showed $P\not= NP$. $\endgroup$
    – Tom van der Zanden
    Jun 28, 2015 at 6:59
  • 1
    $\begingroup$ "This means to show its NP-hard I'd have to do a reduction?" Yes. The only way to show that a problem is NP-hard is to show that every problem in NP reduces to the problem in question, normally by showing that some NP-complete problem does. $\endgroup$
    – David Richerby
    Jun 28, 2015 at 8:20
  • 2
    $\begingroup$ @DavidRicherby Another way would be to show that $P=NP$ and that your problem is not trivial. $\endgroup$
    – Tom van der Zanden
    Jun 28, 2015 at 9:37

0

Reset to default

Browse other questions tagged or ask your own question.