- 122

- 0

## Main Question or Discussion Point

(I asked this question also in Homework Help for Comp Sci and Engineering, but maybe someone in here can answer this)

Im just a little confused about the definition of an NP problem. The most common definition I hear is: a decision problem is in NP if it has a polynomial time certification. So if it is a yes or no question, there is a proof of it in polynomial time. But my question is, when proving a decision problem is in NP, do you have to assume the answer is yes and show a polytime certification exists and then assume the answer is no and show a polytime certification of that answer exists? Or do you choose either yes or no and show that a polytime certification of that answers exists?

Im just a little confused about the definition of an NP problem. The most common definition I hear is: a decision problem is in NP if it has a polynomial time certification. So if it is a yes or no question, there is a proof of it in polynomial time. But my question is, when proving a decision problem is in NP, do you have to assume the answer is yes and show a polytime certification exists and then assume the answer is no and show a polytime certification of that answer exists? Or do you choose either yes or no and show that a polytime certification of that answers exists?