2
$\begingroup$

I have to prove the following problem is in NP (and define verifier as well as the certificate/witness):

The input is a set of $n$ boxes with weights $w_{1},\ldots,w_{n}$ and two numbers $s$ and $t$ (all natural numbers). Can the boxes be loaded onto $s$ trucks if each truck can only carry a total weight of $t$?

Apparently this is supposed to be easy, but I'm stuck.

$\endgroup$
3
$\begingroup$

Once you get the hang of these, they are quite easy, so the first thing is not to over think things.

To prove containment in NP (in this manner) you need (as you mention):

  1. A witness. This is just a "string" that proves an instance is a Yes-instance. So it can just be the solution. When we say "string", typically we don't define how the string is encoded, or even really that the witness is a string. What we give is a format for a solution.
  2. A verifier. This is a Turing Machine that takes a witness (hence why the witness is a string, formally) and the original input, and checks that the witness is correct. So really the verifier is a set of steps to perform this check, given a witness in the correct format. For NP, we have the additional restriction that the verifier has to run in deterministic polynomial time.

So for this problem we can represent a solution as a collection of sets of boxes. We can assume that the boxes have a unique ID. This is the witness. You should, to cement this, try to write done a more precise format for this.

The verifier then should take such a string and check the following:

  1. There are at most $s$ sets (or exactly, depending on the exact problem specification).
  2. That each box appears exactly once, somewhere.
  3. That the total weight of each set is at most $t$.

It should, hopefully, be clear that this verifiers that the solution is correct. The only thing that remains to do, is show that the verifier runs in deterministic polynomial time. Again this should hopefully be fairly clear. Even if we do each step separately, it's three passes over the list (we can, for convenience, assume that the verifier is a multitape machine, so we can more easily represent data structures), and this is certainly polynomial.

$\endgroup$
  • $\begingroup$ Thank you! I really appreciate you taking the time to explain this to me. Could I use a function as the witness that maps the boxes to the trucks? If so, would I still need step 1 of the verifier? $\endgroup$ – Mason Jan 22 '16 at 6:12
  • $\begingroup$ @Mason, yes, you could use a function to do so. Depending on the level of formality required in your proof, it may prove harder to work with. Looking at what you can take away to other similar problems, the "just-write-out-the-answer" approach is very robust. You would still need step one - what if the function you're given maps the boxes to $s+1$ trucks? It still needs to be checked. (Unless you specify the function to be $f: \{1,\ldots,n\} \to \{1,\ldots,s\}$ of course. $\endgroup$ – Luke Mathieson Jan 22 '16 at 8:24
  • $\begingroup$ I did mean a function f:{1,…,n}→{1,…,s}, should have written that in my comment. Yeah, just writing out the answer is something I need to work on; I tend to get lost in "what if" and "could I also do this"-thoughts. Again, thank you! Your answer made the approach to these kinds of problems so much clearer than my professor's lecture could. $\endgroup$ – Mason Jan 22 '16 at 19:29

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.