This Construction of Doesnt Work

Our first instinct about constructing N2i from Aj might be to use a straigiitforward divide-and-conquer approach: if / h J m 2i or fewer moves, then there must be эяЮ К such that both I \- К and К \- J ini moves or fewer. However, if we write down the formula that expresses this idea, say N2i{I,J) = i3K){NiiI,K) A Ni{K,J)), we wind up doubling the length of the expression as we double i. Since г must be exponential in n in order to express all possible computations of M, we would spend too much time writing down N, and N would be exponential in length.

BASIS: For i = 1, Ni{I,J) asserts that either I = or I \- J. We just discussed how to express the condition I - J above. For the condition I \- J, we refer you to the discussion in the next move is right portion of the proof of Theorem 10.9, where we deal with exactly the same problem of asserting that one ID follows from the previous one. The expression Ni is the logical OR of these two expressions. Note that we can write Ni in 0[p{n)) time,

INDUCTION: We construct N2iil, J) from Ni. In the box This Construction of N21 Doesnt Work we point out that the direct approach, using two copies of Ni to build iVj; doesnt give us the time and space bounds we need. The correct way to write N21 is to use one copy of iV in the expression, passing both the arguments {I, K) and {K, J) to the same expression. That is, N2iil, J) will use one subexpression Ni{P,Q). We write N2i{I,J) to assert that there exists ID К such that for all IDs P and Q, either:

1. {P,Q) Ф {I,K) arrd {P,Q) Ф {K,.J) or

2. Ni{P,Q) is true.

Put equivalently, iVj(/,/< ) and Ni{K,J) are true, and we dont care about whether Ni{P, Q) is true otherwise. The following is a QBF for N2i{I, J):

N2i{I,.J) = {3K)(iP)iVQ)[Ni{P,Q) V

PAK = Q)AiK = PAJ = Q))j

Notice that we can write N21 in the time it takes us to write Ni, plus 0{p(n)) additional work.

To complete the construction of N, we must construct iV for the smallest m that is a power of 2 and also at least c+ \ the maximum possible number of moves TM M can make before accepting input w of length n. The number of times we must apply the inductive step above is log2(c), or 0{p{n)). Since eacli use of the inductive step takes time 0{р{п)), we conclude that can be constructed in time 0{p{n)).

Conclusion of the Proof of Theorem 11,11

We have now shown how to transform input w into a QBF

i3Io){3If){S AN AF)

in time that is polynomial in \w\. We have also argued why each of the expressions S, N, and F are true if and only if their free variables represent IDs Iq and that are respectively the initied and accepting IDs of a computation of M on input w, and also loIf. That is, this QBF has value 1 if and only if M accepts w. □

11.3.5 Exercises for Section 11.3

Exercise 11.3.1: Complete the proof of Theorem 11.10 by handling the cases:

a) F - ЕуЕг.

b) F{4x){E).

c) F = (E).

d) F = iE).

*l\ Exercise 11.3.2: Show that the following problem is PS-complete. Given regular expression E, is E equivalent to S*, where S is the set of symbols that appear in £? Hint: Instead of trying to reduce QBF to this problem, it might be easier to show that any language in VS reduces to it. For each polynomial-space-bounded TM M, show how to take an input w for M and construct in polynomial time a regular expression that generates all strings that axe not sequences of IDs of M leading to acceptance of w.

!! Exercise 11.3.3: The Shannon Switching Game is as follows. We are given a graph G with two terminal nodes s and t. There are two players, which we may call SHORT and CUT. Alternately, with SHORT playing first, each player selects a vertex of G, other than s and t, which then belongs to that player for the rest of the game. SHORT wins by selecting a set of nodes that, with s and i, form a path in G from s to t. CUT wins if all the nodes have been selected, and SHOR.T has not selected a path from ,s to t. Show that the following problem is PS-complete: given G, can SHORT win no matter what choices CUT makes?

11.4 Language Classes Based on Randomization

We now turn our attention to two classes of languages that are defined by Turing machines with the capability of using random numbers in their calculation. You are probably familiar with algorithms written in common programming languages that use a random-number generator for some useful purpose. Technically, the fimction randO or similarly named function that returns to you

proof aiKi analysis of Quicksort.ч expected running time can be found in D. E. Knuth, The Art. of Computer Ртодтаттгпд, Vol. HI: Sorting and Searching, Addison-Wesley, 1973.

what appears tn be a random or unpredictable number in fact executes a sjjecific algorithm that can be simulated, although it is very hard to see a pattern in the sequence of numbers it produces. A simple example of such a function (not used in practice) would be a process of taking the previous integer in the sequence, squaring it, and taking the middle bits of the product. Numbers produced by a complex, mechanical process such as this are called pseudo-random numbers.

hi this section, we shall define a type of Turing machine that models the generation of random numbers and the use of those numbers in algorithms. We then define two classes of languages, KP and ZPP, that use this randomness and a polynomial time bound in different ways. Literestingly, these classes appear to include little that is not in P, but the differences are Important. In particular, we shall see in Section 11.5 how some of the most essential matters regarding computer security are really questions about the relationship of these classes to P and AfP.

11.4.1 Quicksort: an Example of a Randomized Algorithm

You are probably familiar with the sorting algorithm called Quicksort. The essence of the algorithm is as follows. Given a list of elements oi, 2,..., a to sort, we pick one of the elements, say oi, and divide the list into those elements that are a-i or less and those that are larger than O]. The selected element is called the pivot. If we are careful with how the data is represented, we can separate the list of length n into two lists totaling n in length in time 0{n). Moreover, we can then recursively sort the list of low (less than or equal to the pivot) elements and sort the list of high (greater than the pivot) elements independently, and the result will be a sorted hst of all n elements.

If we are lucky, the pivot will turn out to be a number in the middle of the sorted list, so the two sublists are each about n/2 in length. If we are lucky at each recursive stage, then after about log2 n levels of recursion, we shall have lists of length 1, and these lists are already sorted. Thus, the total work will be O(logri) levels, each with 0(n) work required, or 0(n logn) time overall.

However, we may not be lucky. For example, if the list happens to be sorted to begin with, then picking the first element of each list will divide the list with one element in the low sublist and all the rest in the high subhst. If that is the case. Quicksort beha\-es much like Selection-Sort, and takes time proportional to n to sort n elements.

Thus, good implementations of Quicksort do not take mechaidcally any ]jarticular position on the list as the pivot. Rather, the pivot is chosen randomly from among all the elements on the list. That is, each of the n elements has probability 1/n of being chosen as the pivot. While we shall not show this claim here, it turns out that the expected running time of Quicksort with tliis