Exercise 1 Question 3 Part 5

Summary:

Is this a decision problem? Why is it even in NP?

Exercise 1 Question 3 Part 5

Jolomb 26 Mar 2016 07:56

Hi,
The question asks us to prove that the problem of finding the partition of players into bands, which minimizes the makespan, is NP-Complete. But that is not a decision problem, and therefore not in NP.
We could ask whether a game has a partition of the players that brings the makespan below a certain threshold K, but that's a diffrent problem.

What am i missing?
Thank you.

Re: Exercise 1 Question 3 Part 5

Israela 26 Mar 2016 12:07

You should prove that it is in NP.

Re: Exercise 1 Question 3 Part 5

Jolomb 26 Mar 2016 14:33

But it's not a decision problem. Finding the partition which minimzes the makespan is not a Yes / No question, NP is a class of decision problems, is it not?

I mean the partition problem that we are asked to reduce to is the Yes /No question whether a group of numbers can be partitioned to two groups with the same sum.

Re: Exercise 1 Question 3 Part 5

Israela 28 Mar 2016 09:02

Minimization and decision problems are (usually) kind of equivalent, because you can solve one of them in polynomial time iff you can solve the other (binary search). Partition also has a version as a minimization problem.

However, it is enough to show that the decision problem is in NP.

Re: Exercise 1 Question 3 Part 5

Tzvika Geft 03 Apr 2016 20:10

Can you formulate the decision problem that we are supposed to show is in NP?

I'm confused about what you expect to see in this question.
If the the current formulation is changed to say "NP hard" at the end, then I'm fine with it.

Re: Exercise 1 Question 3 Part 5

Israela 04 Apr 2016 11:31

(generally for minimization problems:) decide whether the value that you want to minimize is smaller then given k

Re: Exercise 1 Question 3 Part 5

TheStudent 04 Apr 2016 14:28

Do you mean that we should show that next problem is NP-Complete: does the minimum makespan smaller than K?

Last edited on 04 Apr 2016 14:34 by TheStudent Show more

Re: Exercise 1 Question 3 Part 5

noammor 04 Apr 2016 18:12

The following problem:

Given S, S1 and S2, are S1 and S2 a partition of S that minimizes the makespan?

is in coNP. A verifier for S1 and S2 not being a partitioning that minimizes the makespan is easy to formulate - just accept a different partitioning of S and calculate its makespan.

Since it's in coNP I don't think we can prove that it's NP-complete.

The following problem is in NP:

Given S and k, is there a partitioning of S with makespan less than k?

One may try to think of a scheme to verify the following problem by applying the above verifier repeatedly:

Given S, what is the minimal makespan of any partition of S?

But I really can't see how. Binary search won't work since S's elements can be arbitrarily large.

Last edited on 04 Apr 2016 18:28 by noammor Show more

Re: Exercise 1 Question 3 Part 5

Israela 04 Apr 2016 21:19

Read my previous answer.

(Binary search works because you know the set of critical values, but that's not a complexity\optimization course, so it really doesn't matter).