9.3 NP vs Co-NP

Question 1

What is the complement of a decision problem

And how does it impact NP and cook reductions

Answer 1

• A negation of the problem (ie yes instances become no instance)
• Is satisfiable => is unsatisfiable
• Cook reductions still work (can just negate output)
• Doesn’t imply NP as the witness is the bottleneck

Question 2

What is Co-NP

Answer 2

• Set of decision problem’s whose compliment is in NP
• Note every compliment of an NP problem is necessarily in Co-NP since not not cancels out

Question 3

What is a Karp reduction (and how does it differ from and equate to a cook reduction)

Answer 3

• Karp reduction implies that X is a special case of Y. Ie can construct a single Y instance from an X instance
• Both have to be Yes instances
• Mapping f: X -> Y has to be polynomial
• Must both be decision problems
• Karp reduction implies a cook reduction

Question 4

What does it mean for a problem to be NP hard/complete under Karp reductions

Answer 4

• Every problem is Karp reducable to it
• Is also in NP (for complete)

Question 5

What does it mean for a problem to be Co-NP hard/complete under Karp reductions

Answer 5

• Every problem is Karp reducable to it
• Is also in NP (for complete)

Question 6

Are most of the reductions we studied also Karp reductions?

Answer 6

Yes. Mapping once instance to another.

Question 7

Are cook and karp reductions the same? Which is commonly used for Hard vs Complete?

Answer 7

• No. But most of the time they are. Ie some problems where cook doesn’t imply karp (but not vice versa)
• Hard = Cook. Complete = Karp (and thus Karp hard too).