World's most popular travel blog for travel bloggers.

Can someone provide an introductory example of a certificate in complexity theory?

, , No Comments
Problem Detail: 

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?

Asked By : Beached Whale
Answered By : Juho

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.

The example you mention is a problem that is also in P (clearly, we can solve it in polynomial time). Every problem in P is also in NP. We don't have to care about the certificate, but instead we can simply solve the problem in polynomial time. (Check the definition of NP if this feels confusing, but hopefully it doesn't).

You might also enjoy the question How can I verify a solution to Travelling Salesman Problem in polynomial time?

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback