• Support PF! Buy your school textbooks, materials and every day products Here!

NP problems

  • Thread starter ak416
  • Start date
  • #1
122
0
1. Homework Statement

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. Homework Equations



3. The Attempt at a Solution
 

Answers and Replies

Related Threads for: NP problems

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
0
Views
886
Replies
1
Views
602
Replies
1
Views
1K
  • Last Post
Replies
2
Views
561
  • Last Post
Replies
14
Views
3K
  • Last Post
Replies
0
Views
1K
Replies
2
Views
3K
Top