CSE396 Problem Set 11 Answer Key Spring 2010 (1) The reduction to recall takes a TM M and a string w, and builds M' as: Input y Simulate M(w) If and when it accepts, accept y. [If M rejects w, reject y] As shown in lecture, if M accepts w then L(M') = \Sigma*, while if M does not accept w, then L(M') = \emptyset. Among the strings y in question, one of them happens to be the code M' of M'. Thus we have: M accepts w ==> L(M') = \Sigma* ==> M' accepts its own code. M does not accept w ==> L(M') = \emptyset ==> M' does not accept its own code. Thus \in A_TM <==> M' \in K, so A_TM mapping-reduces to K. This is via the same reduction function as for A_TM <=_m NE_TM and A_TM <=_m ALL_TM. (2) The first idea that comes to mind is to modify the above reduction: M' = Input y Simulate M(w) [or for a reduction from K_TM, run M(M)] If and when it accepts, accept y if y = M, reject otherwise. Then \in A_TM ==> L(M') = {M}, and \notin A_TM ==> L(M') is empty. The rub is that in the first case, to conclude M' \in S = {M: L(M) = {M} }, we actually need L(M') = {M'}, not {M}. Using the supposition that M' can generate its own code, and reducing from K_TM not A_TM as requested, build: M' = Input y Generate the code of M'; if y doesn't equal it, reject. Simulate M(M) If and when M(w) accepts, accept y (which == M'). Then M \in K_TM ==> M(M) accepts ==> L(M') = {M'} ==> M' \in S, while M \notin K_TM ==> M does not accept M ==> L(M') = \emptyset ==> M' \notin S. Clearly the code of M' can be built from the code of M, so this is a mapping reduction from K_TM to S. This shows that S is not only undecidable, it's not co-r.e. either. (Always recall, "r.e.", "c.e.", "Turing-recognizable", and my preferred "Turing acceptable" are synonyms.) To show that S is not r.e., we need another reduction, from D_TM this time. Given any M, we can build g(M) = M" like so: M" = Input y Generate the code of M"; if y equals it, *accept*. Else simulate M(M) for |y| steps. If M accepted M in that time, then *accept y*, else *reject y*. The function g that builds this code is computable, so this is a mapping reduction. If M \in D_TM, then M does not accept its own code, so the only string y accepted by M" is the one that equals its own code, so L(M") = {M"}, so M" \in S. While if M \notin D_TM, then M does accept its own code, in some number r of steps. Then for all y of length >= r, the last line "kicks in" and M" accepts y. This is enough to destroy L(M") being just {M"}, so M" is not in S. Thus we have, for all TMs M: M \in D_TM <==> g(M) \in S. This implies that S is not r.e. The two reductions together imply that S is neither c.e. nor co-c.e. If one instead defines S' = {M: L(M) = {abba}}, then change the code bodies of M' and M" in the above reductions to make reductions f' and g': M' = Input y If y != "abba", reject. Simulate M(M) If and when M(w) accepts, accept y (which == "abba"). M" = Input y If y == "abba", accept. Else simulate M(M) for |y| steps. If M accepted M in that time, then *accept y*, else *reject y*. These give M \in K_TM <==> f'(M) = M' \in S', and M \in D_TM <==> g'(M) = M" \in S', so S' is neither c.e. nor co-c.e. either. (3) Given an instance of the Acceptance Problem, first produce the TM M' from problem (1). Then map M' to the grammar G' such that L(G') equals the complement of V_{M'}. Then we have: \notin A_TM ==> M' \in E_TM ==> V_{M'} = \emptyset ==> L(G') = Sigma* which ==> L(G') is regular, since Sigma* is regular. Meanwhile \in A_TM ==> M' \in ALL_TM (which is stronger than M' \notin E_TM) ==> V_{M'} has accepting computations for every input x ==> V_{M'} is not regular [the "fact"---try proving this by imitating the Myhill-Nerode proof for {xx: x \in {0,1}*}] ==> the complement of V_{M'} is not regular ==> L(G') is not regular. Footnote: One *can* do a reduction from E_TM directly by modifying the grammar to accept a "tandem" language: Given M build G_M for the complement ~V_M from the notes, with start symbol S_M, and then make G with these rules: S --> S_M # A | A # B A --> 0A | 1A | epsilon B --> 0B1 | epsilon If L(M) is empty, then S_M derives {0,1}^* (under binary encoding of computations), and since A does likewise, you get the language (0+1)*#(0+1)*, which is regular. But if L(M) is not empty, then there is some string y that S_M does not derive---namely, y coding an accepting computation of M on some input. The only way a string beginning with y# can be derived from S is by following it with 0^n 1^n for some n. A Myhill-Nerode proof with S = y#0* thus shows that L(G) is nonregular. Thus with this modified reduction f(M) = G, we get M \in E_TM <==> L(G) is regular, so REGULAR_CFG is undecidable. [In point of fact, it is neither c.e. nor co-c.e.] (4) In order to check whether a given graph G = (V,E) contains a triangle, we only need to enumerate all combinations of three vertex and check if these three vertices form a triangle. The algorithm has three nested for-loops running i,j,k from 1 to n = |V|. Letting E(i,j) stand for "G has an edge from i to j", we get: for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { if (E(i,j) && E(j,k) && E(k,i)) { accept; } } } } //control here means no triangle reject; Running time is clearly O(n^3), owign to the three nested loops. The worst-case running time, which happens when G has no triangle is \Theta(n^3). Actually, given that the graph may have N ~= n^2 edges, with N not "n" being a better gauge of the size of the input, the running time is order-of N^{1.5}, which sounds better. Either way, the running time is bounded by a polynomial in n or N, so the TRIANGLE problem belongs to P. This assumes that G can't have self-loops, i.e. E(i,i) is always false. If it does, then to avoid a self-loop being part of a triangle, we can code the loops to skip over cases where two indices are equal. Since g was stated to be undirected, one can avoid this problem by running j from i+1 to n, and k from j+1 to n. This reduces the absolute running time, but the order of the time remains cubic in n, so it doesn't change the asymptotic classification of the problem. (5) First show that the given language is in NP. For a given set of equations, just nondeterministiclly guess one 0-1 assignment for variables x_1,x_2, \ldots, x_n, and check that each equation is satisfied. The only operations used in polynomials are addition, subtraction, and multiplication, and these are computable in time that is polynomial in the number d of digits. (The worst that can happen is that a k-fold multiplication multiplies d by k in terms of the length of the answer, which stays quadratic insofar as the overall length of the equations involves d and k.) Since the coefficients and arguments are integers, there are no fractions and no issues of numerical precision. Hence the "verifying" part is in polynomial time, and so the language belongs to NP. Next, we need to show the given problem is NP-complete by reduction from 3SAT. For each instance of 3SAT, it is in the form of h = C_1 && C_2 && ... && C_m, where each clause C_j is in the form (a v b v c). Here each of a,b,c is either a variable, i.e. x_i, for some i, or the negation of variable, i.e. ~x_i. We convert h into a set of equations E_j(x_1, x_2, ..., x_n) = 1, over all j = 1 to m, in this way: (a v b v c) ==> (a v b) v c ==> abc - ab - ac - bc + a + b + c. This clearly has value 0 when a = b = c = 0, and you can check that it has value 1 under the other seven 0-1 assignments. (It is obtained by iterating the idea a v b ==> a + b - ab.) Then for each of a,b,c, substitute x_i if it is a variable x_i, or 1-x_i if it is a negation ~x_i. Solutions to the resulting equations with 0-1 arguments are then in 1-1 correspondence with satisfying assignments to h, so in particular h is satisfiable iff the equations are solvable by a 0-1 assignment. Since the translation to equations is so direct for each clause, it is computable in polynomial (in fact, linear) time. Thus 3SAT polynomial-time mapping reduces to the equation problem, so the latter is likewise NP-complete.