U.C. Berkeley — CS172: Automata, Computability and Complexity Solutions to Problem Set 7
Professor Luca Trevisan
4/6/2007
Solutions to Problem Set 7
1. Let A and B be two languages. Then show that:
(a) IfAandBareinNP,thensoareA[BandA\B.
(b) If A and B are NP-complete, then A [ B and A \ B need not be NP-complete. [10 + 15 = 25 points]
Solution:
(a) If A is in NP, then there is a deterministic Turing machine (verifier) VA such that x 2 A if and only if 9y |y| p(|x|) and VA accepts hx, yi (see Sipser, page 265-266). Similarly, we have a machine VB for B.
Then for the language A [ B, we define the machine VA[B, which runs both VA and VB on the given input and accepts if either does. For x 2 A [ B, there is a string yA such that VA accepts hx,yAi or a string VB accepts hx,yBi. Taking y to be yA or yB (whichever exists), VA[B will accept hx,yi. Similarly, for A \ B, we can define VA\B, which takes an input hx,yA,yBi accepts if and only if VA accepts hx,yAi and VB accepts hx, yB i.
(b) We argue about intersection first. Let L be any NP-complete language. Then we define the languages
A = 0L = {0x | x 2 L} B = 1L = {1x | x 2 L}
Then we can see that both A and B are NP-complete. This is so because any reduction from (say) SAT to L can be converted to a reduction to A by adding a 0 to the output and similarly for B. It is also easy to see that they are both in NP if L is. But then A \ B = ; which cannot be NP-complete.
One can derive the argument for union by exactly the same reasoning by noticing that if A and B are NP-complete, then A and B are co-NP complete and showing that A [ B is not NP-complete is the same as showing that A \ B is not co-NP complete. Thus, for an NP-complete language L, we can take A = 0L and B = 1L. This gives
A = 0L = (1{0, 1}⇤) [ {0x | x 2 L} B = 1L = (0{0, 1}⇤) [ {1x | x 2 L}
Also, note that reductions to L can be easily modified to reductions to reductions to A and B, by appending 0 and 1 respectively at the beginning. Thus, A and B are NP-complete. However, A [ B = {0, 1}⇤, which cannot be NP-complete.
2. Let U = {hM,x,#ti|NDTM M accepts input x within t steps on at least one branch}. Show that U is NP-complete.
[15 points]
1
Solution: Given any NP language L, we have an NDTM ML such that 8x 2 L, ML accepts x on at least one branch in at most pL(|x|) steps, where pL() is a fixed polynomial depending on the machine. Also, ML does not accept any x 2/ L. Then, given x, we create y = hML,x,#pL(|x|)i in polynomial time. By the previous argument, x 2 L i↵ y 2 U. Thus, U is NP-hard.
To show that U is also in NP, we can create an NDTM MU, which given an input u = hM,x,#ti, simulates M on x for t steps. MU nondeterministically guesses all the branches of M and accepts u i↵ M accepts u. Since the input has length at least t and we simulate M for at most t steps, the running time is polynomial in the length of the input (note this is the reason we need t in unary). It is easy to see that MU accepts exactly the language U, thus proving U 2 NP. Hence, U is NP-complete.
3. For a function g : N ! N, we say a language L is in SIZE(g(n)) if there exists a family of circuits C1, C2, . . . (with Ci having i inputs and one output) such that:
• 8n2NthesizeofCn isatmostg(n) • 8×2{0,1}n x2L,Cn(x)=1.
In the class we saw a proof that SIZE(2o(n)) ( SIZE(2n) i.e. for every large enough n there exists a function f : {0,1}n ! {0,1} that is not computable by circuits of size 2o(n). This problem asks you to show such a “separation result” for a smaller function. Show that SIZE(n3/100 log n) ( SIZE(n3).
[20 points]
Solution: We saw is class that any circuit of size S can be described by 4S log(2S) bits. Hence, any circuit of size n3/100 log n can be described by 4· n3 ·log ⇣ n3 ⌘ < 12n3/100
100 log n 100 log n bits. Thus, the number of functions in SIZE(n3/100 log n) is at most 212n3/100.
However, we also know that any function on k bits can be computed by circuits of size at most 3 · 2k 4. We then consider the set B of all the functions which only look at the first log(n3/5) bits of the input. There are 2n3/5 such functions. Hence, SIZE(n3/100 log n) ( B, since 2n3/5 > 212n3/100. But all these functions can be computed by circuits of size at most 3 · 2log(n3/5) 4 3n3/5 < n3. Hence B ⇢ SIZE(n3). Thus, we have
SIZE(n3/100 log n) ( B ⇢ SIZE(n3) ) SIZE(n3/100 log n) ( SIZE(n3)
2