Introduction to Automata Theory, Languages, and Computation

Solutions for Chapter 11

Solutions for Section 11.3

Solutions for Section 11.5

Solutions for Section 11.1

Exercise 11.1.1(a)

The complement of TRUE-SAT consists of all inputs that are not well-formed expressions, inputs that are well-formed expressions but that are false when all variables are true, and well-formed expressions that are true only when all variables are true. We shall show TRUE-SAT is NP-complete, so it is unlikely that the complement is in NP.

To show TRUE-SAT is NP-complete, we reduce SAT to it. Suppose we are given an expression E with variables x1, x2,..., xn. Convert E to E' as follows:

1. First, test if E is true when all variables are true. If so, we know E is satisfiable, and so convert it to a specific expression x+y that we know is in TRUE-SAT.

2. Otherwise, let E' = E + x1x2...xn, surely a polynomial-time reduction. Surely E' is true when all variables are true. If E is in SAT, then it is satisfied by some truth assignment other all all-true, because we tested all-true and found E to be false. Thus, E' is in TRUE-SAT. Conversely, if E' is in TRUE-SAT, then since x1x2...xn is true only for the all-true assignment, E must be satisfiable.

Exercise 11.1.2

1. To show the language is in NP, guess z, compute f(z) deterministically in polynomial time, and test whether f(z) = x. When the guess of z is correct, we have f ^-1(x). Compare it with y, and accept the pair (x,y) if z < y.

2. To show the language to be in co-NP, we have to show the complement --- the set of inputs that are not of the form (x,y), where f ^-1(x) < y, is in NP. It is easy to check for ill-formed inputs, so the hard part is checking whether f ^-1(x) >= y. However, the trick from part (1) works. Guess z, compute f(z), test if f(z) = x, and then test if z >= y. If both tests are met, then we have established that f ^-1(x) >= y, so (x,y) is in the complement language.

3. Finally, we must show that the language is not in P. We can show that if it were in P, then with n tests for membership in the language, we could binary-search to find the exact value of f ^-1(x). If one test takes time that is polynomial in n, then n times that amount is also polynomial in n. Start by testing the pair (x,2^n-1), i.e., the rough midpoint in the range of n-bit integers. If the answer is ``yes,'' next test (x,2<sup>n-2</sup>); if the answer is ``no,'' test (x,3*2^n-2) next. In this manner, we can establish one bit of f ^-1(x) at each test, and after n tests, we know f ^-1(x) exactly.

   Return to Top

   Solutions for Section 11.3

   Exercise 11.3.2

   Suppose M is a TM with polynomial space bound p(n), and w is an input to M of length n. We must show how to take M and w, and write down, in polynomial time, a regular expression E that is Sigma* if and only if M does not accept w.

   Technically, this construction reduces L(M) to the complement of the set in question, that is, to the set of regular expressions that are not equivalent to Sigma*. However, an easy consequence of Theorem 11.4 is that, since a deterministic, polynomial-time TM can be made to halt, PS is closed under complementation; just change the accepting states to halting, but nonaccepting states, add an accepting state, and make every halting, nonaccepting state transfer to that accepting state instead of halting immediately. Thus, we could assume that M is actually a TM for the complement of the language L in PS in question. Then, we are actually reducing L to the language of regular expressions equivalent to Sigma*, as requested.

   To construct regular expression E, we shall write E = F + G + H, where the three subexpressions E, F, and H define sequences of ID's of M that do not ``start right,'' ``move right,'' and ``finish right,'' respectively. Think of an accepting computation of M as a sequence of symbols that are the concatenation of ID's of M, each preceeded by a special marker symbol #. The alphabet Sigma for E will be # plus all the tape and state symbols of M, which we can assume without loss of generality are disjoint. Each ID is exactly p(n)+1 symbols long, since it includes the state and exactly p(n) tape symbols, even if many at the end are blank.

   1. H: Finishes wrong. M fails to accept if the sequence has no accepting ID. Thus, let H = (Sigma - Qf)*, where Qf is the set of accepting states of M.

   2. F: Starts wrong. Any string in which the first p(n)+2 symbols are not #, q_0 (the start state), w, and p(n) - n blanks, is not the beginning of an accepting computation, and so should be in L(E). We can write F as the sum of the terms:
      • (Sigma-{#})Sigma*, i.e., all strings that do not begin with #.
      • Sigma(Sigma-{q_0})Sigma*, i.e., all strings that do not have q_0 as their second symbol.
      • Sigmaⁱ⁺¹(Sigma-{a_i})Sigma*, where a_i is the ith position of w. Note Sigma^k stands for Sigma written k times, but this expression takes only polynomial time to write.
      • Sigmaⁱ(Sigma-{B})Sigma*, for all n+3 <= i <= p(n)+1. Here, B represents the blank, and this expression covers all strings that fail to have a blank where the first ID must have one. Note that these terms require us to write Sigma as many as p(n)+1 times, but that still takes only polynomial time. Also, there are polynomially many terms, so the total work is polynomial.
      • (Sigma + ε)^p(n)+1. This term covers all strings that are shorter than p(n)+2 symbols, and therefore cannot have an initial ID, regardless of the symbols found there. As in the previous set of terms, the time taken to write this term is large, but polynomial.

   3. G: moves wrong. We need to capture all strings that have some point at which symbols separated by distance roughly p(n) do not reflect a move of M. The idea is similar to that used in Cook's theorem (Theorem 10.9). Each position of an ID is determined by the symbol at that position in the previous ID and the two neighboring positions. Thus, G is the sum of terms (Sigma*)UVW(Sigma^p(n))X(Sigma*), where U, V, W, X are four symbols of Sigma such that if UVW were three consecutive symbols of an ID of M (U may be # if the ID is just beginning, and W may be # if the ID is ending), then X would not be the symbol in the same position as V in the next ID. For example, if none of U, V, W are a state, then X could be any symbol but V. Again, we can write this large expression in polynomial time, even though it requires us to write Sigma p(n) times.
   If M accepts w, then there is some accepting computation, and the string representing that computation fails to match any of the regular expressions described above. Thus, E != Sigma*. However, any string that is not an accepting computation of M on w will surely fail meet one of the conditions ``starts wrong,'' ``moves wrong,'' or ``finished wrong,'' and therefore will be in L(E). Thus, if M does not accept w, then E = Sigma*.

   Return to Top

   Solutions for Section 11.5

   Exercise 11.5.1(a)

   A simple way to to observe that 9 - 11 = -2, and -2 modulo 13 is 11, since 13 -2 = 11. Or, we may treat the subtraction as addition of a negative number, say that -11 modulo 13 is 2, and 9 + 2 modulo 13 is 11.

   Exercise 11.5.1(c)

   We need to compute the inverse of 8 modulo 13. Exploring the possibilities, from 2 to 12, we find that 8*5 = 40, which is 1 modulo 13. Thus, 1/8 = 5 modulo 13, and 5/8 = 5*5 = 25 = 12 modulo 13. Thus, 5/8 = 12.

   Exercise 11.5.3(a)

   From the table of Fig. 11.9, we see that 2*2 = 4, 3*3 = 2, 4*4 = 2, 5*5 = 4, and 6*6 = 1. We also know that 1*1 = 1. Thus, 1, 2, and 4 are the quadratic residues modulo 7.

   Return to Top