Description
Problem 1
Prove or disprove: P ⊆ NP
Problem 2
Consider problem 9-13 from the text.
(a) Prove that Hitting Set ∈ NP.
(b) Prove that Hitting Set is hard for NP.
(c) Prove that Hitting Set is complete for NP.
Problem 3
Do problem 9-10 from the text.
Problem 4
Do problem 9-16 from the text.
Problem 5
Do problem 9-24 from the text.
1