Models of Computation - Mathematics 352 - Fall 2009

For HW #21

1. Carefully read the definition of class NP in Wilf, page 179, 3rd paragraph, including the last sentence of that paragraph. Referring to the last sentence, why do we not require the verification algorithm to run in polynomial time as a function of the sum of the lengths of x and C(x)?
   Hint: See problem VII in Extra Problems for HW #19.
2. Wilf doesn't really explain the standard definition of a Non-Deterministic Turing Machine (NDTM).  Roughly speaking, an NDTM is a Turing machine that for some configurations has a choice of more than one action to take. Here's an example:
   q1 1 0 q2
   q2 0 R q1
   q2 0 1 q3
   
   Note that the second and third instructions both start with the configuration "q2 0" (by a configuration I mean the pair (q,s) where q is the state the machine is in and s is the symbol the machine head is reading).  Here's how this machine works: Whenever the machine is in state q2 and reading 0, it randomly performs either the 2nd or the 3rd instruction. (Don't worry about what function this Turing machine actually computes; it doesn't matter.)  Thus, if we run a NDTM a second time with the same input, it may give a different output! Hence the adjective "non-deterministic."
   
   Here is a definition of NP found in some textbooks.
   Definition: a problem is said to be in NP if there is a NDTM that, given any instance of the problem, stops in polynomial time and outputs 0 or 1, subject to the following two conditions:
   (1) If the answer to the given problem instance is No, the NDTM outputs 0.
   (2) If the answer to the given problem instance is Yes, the NDTM may output 0 or 1, but it must output 1 at least some of the time (i.e., with nonzero probability).
   Thus, when we see an output of 1, we know for sure that the answer is Yes; but an output of 0 tells us nothing. In a way, when the machine outputs 0, it's saying "I don't know!"
   
   Suppose we want to build a NDTM for the graph coloring problem. Explain why none of the following NDTMs proves that the graph coloring problem is in NP. Note: each NDTM below uses the symbols 0 and 1 only (and B represents a blank square, as usual).
    
   1. NDTM #1:
      q1 B 0 q2
      q1 0 0 q2
      q1 1 0 q2
       
   2. NDTM #2:
      q1 B 1 q2
      q1 0 1 q2
      q1 1 1 q2
       
   3. NDTM #3:
      q1 B 0 q2
      q1 B 1 q2
      q1 0 0 q2
      q1 0 1 q2
      q1 1 0 q2
      q1 1 1 q2
      
       
3. Note that in the above definition of NP, there is no mention of certificates! This definition sounds very different from Wilf's. But they are equivalent! Can you see how? It's not obvious, but try to figure it out on your own if you can. If you don't succeed, try to search the web for an explanation of why the two definitions are equivalent. Once you see the connection between the two definitions, write a paragraph or two explaining what you understand.
4. What is the difference between "NP", "NP-hard", and "NP-complete"? Read Wilf p.172-173 and search the web to find answers!