Models of Computation - Mathematics 450 - Fall 2006

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. [Optional] Wilf doesn't really explain the standard definition of a Non-Deterministic Turing Machine (NDTM). Here is a succinct definition, provided by the National Institute of Standards and Technology:
   
   • Definition: A Turing machine which has more than one next state for some combinations of contents of the current cell and current state. An input is accepted if any move sequence leads to acceptance.

   Here's an example:
   q1 1 0 q2
   q2 0 R q3
   q2 0 L q3
   
   Note that the second and third instructions both start with "q2 0." How does such a machine work? Whenever the machine is in state q2 and reading 0, it "randomly" picks and performs one of the 2nd and 3rd instructions. Hence the adjective "non-deterministic." How does this correspond to the above definition? Read the definition again! When the machine is in state q1 and is reading 1, there is more than one "next state." Thus, if you run a NDTM more than once with the same input, it may give a different output each time!
   
   Now, here is a definition of NP found in many 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 may not output 0 all the time. In other words, it must output 1 with a 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 telling us "I don't know!"  (Don't confuse this with partial decidability; they are analogous but very different.)
   
   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? Write a paragraph explaining this.