EXERCISES ON NP-COMPLETENESS



 1. Which of the following can we infer from the fact that the traveling
    salesperson problem is NP-complete, if we assume that P is not equal to NP?

    (a) There does not exist an algorithm that solves arbitrary instances of
        the TSP problem.
    (b) There does not exist an algorithm that efficiently solves arbitrary
        instances of the TSP problem.
    (c) There exists an algorithm that efficiently solves arbitrary instances
        of the TSP problem, but no one has been able to find it.
    (d) The TSP is not in P.
    (e) All algorithms that are guaranteed to solve the TSP run in polynomial
        time for some family of input points.
    (f) All algorithms that are guaranteed to solve the TSP run in exponential
        time for all families of input points.


 2. Which of the following can we infer from the fact that PRIMALITY is in NP
    but not known to be NP-complete, if we assume that P is not equal to NP?

    (a) There exists an algorithm that solves arbitrary instances of PRIMALITY.
    (b) There exists an algorithm that efficiently solves arbitrary instances
        of PRIMALITY.
    (c) If we found an efficient algorithm for PRIMALITY, we could 
        immediately use it as a black box to solve TSP.


 3. Which of the following are NP-complete?

    (a)  The brute force TSP algorithm.
    (b)  The quicksort algorithm for sorting.
    (c)  The Halting problem.
    (d)  Hilbert's 10th problem.


 4. Let X and Y be two decision problems.  Suppose we know that X reduces
    to Y. Which of the following can we infer?

    (a)  If Y is NP-complete then so is X.
    (b)  If X is NP-complete then so is Y.
    (c)  If Y is NP-complete and X is in NP then X is NP-complete.
    (d)  If X is NP-complete and Y is in NP then Y is NP-complete.
    (e)  X and Y can't both be NP-complete.
    (f)  If X is in P, then Y is in P.
    (g)  If Y is in P, then X is in P.