College of Computer & Information Science Spring 2009 Northeastern University Handout 9 CSG714: Theory of Computation 9 February 2009

Problem of the Week – 5

Reductions and NP

This problem concerns two questions that came up in last class’s discussions. First was whether there exists NP-hard problems that are not in NP. The answer is certainly yes, since there are problems in much higher complexity class to which every language in NP reduces to in polynomial time. In fact, as an extreme, we can take an undecidable problem, say the Halting Problem. Show that the Halting Problem is NP-hard.

We also discussed the difference between Karp or many-one reductions or mapping reductions (as defined in Sipser) and Cook or Turing reductions. A polynomial-time reduction from language L_{1} to L_{2} means that one can construct a Turing machine for deciding L_{1} by making polynomiallymany calls to a given Turing machine that decides L_{2}. Show that NP is closed under many-one reductions. Why does not a similar proof extend to Turing reductions?