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 inefficient.
     (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.  We can infer only (a).

     (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.