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.
Proof that this problem is in NP
complexity theory;np
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):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.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:There are at most $s$ sets (or exactly, depending on the exact problem specification).That each box appears exactly once, somewhere.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.