Models of Computation - Mathematics 450 - Spring 2005

For HW #26

1. Wilf, page 180, line -10:  ... (how can we recognize a set of clauses that is satisfied by assigning to every variable the value 'T'?)
   One way is of course to evaluate every literal and then every clause, and see if all clauses are satisfied. But there is a nice and simple shortcut. What is it?
2. Let G be the 3-vertex graph whose second vertex is connected (adjacent) to its first and third vertices, and there are no other edges (i.e., G has exactly two edges). Consider the question "Is G 2-colorable?"  Repeat Example 5.2 (page 181) for this instance of Graph Coloring; i.e., write out the clauses we get after reducing "Is G 2-colorable?" to SAT. (You should get a total of ten clauses, I believe.) Then use a truth table to determine whether or not the instance of SAT that you obtained is satisfiable. What do you get, and how does this correspond to the expected solution for "Is G 2-colorable?"
3. 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 VI in Extra Problems for HW #24.
4. Wilf doesn't really explain the standard definition of a nondeterministic 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." Note also that this corresponds to the above definition since we can think of the first instruction as having more than one "next state." Thus, if you run a NDTM several times 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!"  But don't confuse this with partial decidability; they are 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.