# Does the problem belong to NP class?

So I am studying for my Algorithm theory exam and this is the problem i could not solve:

Given numbers $$x_1, x_2, ..., x_n$$ which are the sizes of $$n$$ files and disk capacity $$D$$. Determine if you can seperate these files into $$3$$ disks so that, in every disk sum of doesn't exceed $$D$$. Justify that this problem belongs to class NP

So i am thinking you can seperate only if:
$$x_i < D$$ and if $$x_1 + x_2 + ... + x_n > 3\cdot D$$
Are these the only rules?

## 1 Answer

Nobody asked you to give conditions on when that happens. Also, your second condition is incorrect: if all $$x_1,...,x_n$$ are 0 then for any $$D$$ there is a solution.

What you are asked is to show this is in NP, hence, show a "prover-verifyer" solution:

The proof will be the following: for each $$1\le i\le n$$, the proof at index $$i$$, is $$p_i$$ and will be one of three numbers ($$1,2,3$$ for example) that will indicate in which disk we want to put the file $$x_i$$. Then, just check that for every one of the three disks, the sum of the $$x$$'s in it do not exceed $$D$$.

Its not hard to show why this algorithm is correct, so I will leave it for you to try on your own.