Assignment 8

Home

NP-Completeness and Reduction

Related Reading:

Chapters 34, 41, and 54 in the Omnibus.

Due:  Midnight Sunday April 6, 2008

(Look ma, no Haskell programming! :-)

  1. Do Problem 2 in Chapter 34 of the Omnibus.
     
  2. Do Problem 3 in Chapter 54 of the Omnibus.
    (Note:  "VC" is the "vertex covering" problem described in Problem 1 in Chapter 41).
     
  3. Suppose that I have an O(n2) reduction from a problem P to a problem Q.  Then:
    bulletIf I have an algorithm for solving P in time O(n logn), how quickly can I solve Q?
    bulletIf I have an algorithm for solving Q in time O(n logn), how quickly can I solve P?
     
  4. Prove that the following decision problems are undecidable:
    bulletGiven two programs P and Q and an input X, answer "yes" if either both P and Q halt on X or both P and Q do not halt on X, and answer "no" otherwise.
    bulletGiven a program P and two separate inputs X and Y, answer "yes" if P halts on both X and Y, and answer "no" otherwise.
    bulletGiven a program P and an input X, answer "yes" if P either does not halt on X or it halts and produces 42 as a result, and answer "no" otherwise.

    Hint:  Use a reduction argument involving the Halting Problem for each, but be sure that you do the reduction in the right direction!

     

 Solution.