ak416
Feb1-07, 10:51 PM
1. The problem statement, all variables and given/known data
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? I hope somebody can help me because I have an assignment due tomorrow asking me whether certain problems are in NP.
2. Relevant equations
3. The attempt at a solution
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? I hope somebody can help me because I have an assignment due tomorrow asking me whether certain problems are in NP.
2. Relevant equations
3. The attempt at a solution