EXERCISES ON NP-COMPLETENESS

READING 
-------
  Lecture notes for NP-completeness.
  Notes on Computability and Intractability.


EXERCISES
---------

 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 the
    PRIMALITY problem 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 arbitary
        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 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.















		  ----------------------------------
		  ANSWERS TO EXERCISES ON NP-COMPLETENESS


 1.  We can infer (b) and (d) only.

     (a)  The brute force TSP algorithm always works. (It's just painfully slow.)

     (b)  If P != NP, then there does not exist an efficient algorithm
          for any NP-complete problem, including TSP.

     (c)  We could infer this if P = NP.

     (d)  If P != NP, then no NP-complete problem can be in P.

     (e)  The brute force TSP algorithm always takes N! steps to solve a
          problem with N points. This is not polynomial.
     
     (f)  There may be easy instances. E.g., if all the TSP points lie on
          a line (or the boundary of a circle).

2.  (a) only.

     (a)  All problem in NP are solvable.

     (b)  There are problems in NP that are neither in P or NP-complete (assuming P != NP).
          PRIMALITY could be one of them.

     (c)  This cannot be inferred since we don't know if PRIMALITY is NP-complete.
          (Note that the discovery of an efficient algorithm for TSP would immediately
          imply the discovery of an efficient algorithm for TSP.)


3.  None. NP-completeness deals with *problems* not specific algorithm for problems.
    The Halting problem and Hilbert's 10th problem are undecidable, so they are not in
    NP (and all NP-complete problems are in NP).

4.  (d) and (g) only

    X reduces to Y means that if you had a black box to solve Y efficiently, you could use
    it to solve X efficiently. X is no harder than Y.