# Can someone provide an introductory example of a certificate in complexity theory? [duplicate]

Just stepping into complexity theory, I am befuddled by this notion of a certificate and can't find any utility of this concept.

From my understanding, a certificate is used when you are trying to ascertain whether a problem is NP...a problem is NP if you can verify a p-time solution exist or not (co-NP). I cannot see why you would need a certificate to perform this solution finding. And how is certificate different from "verification".

For example, if I were to try to prove whether all elements in a set is divisible by some number (say 3). Say I then brute force divide all elements by 3 and sees that indeed all elements in this set is divisible by 3. Now where in this process would a certificate come into play?

Also, how would you go about to physically construct a certificate?

Suppose you are the verifier for SUBSET-SUM: "given a set $S$ of integers, is there a subset of $S$ whose elements sum up to exactly zero?" To show the problem is in NP, you must be able to efficiently verify that a solution I give you is correct. As the verifier, you only care about verifying solutions (not "finding solutions"!). You do not care where that solution might come from or who constructs it. Now, when you are given a subset, you can easily sum up the elements and announce whether or not those elements sum up to 0.