Question

Closure properties of P and NP. (a) Is P closed under union, intersection, concatenation, complement and star? Just answer ”yes” or ”no” for each operation. (b) Is NP closed under union, intersection, concatenation, complement and star? Just answer ”yes” or "no" for each operation.

Answer 1

page closure pooperty for p :- closed under) yes union :-) let L1, L2 EP and Mio M2 be deterministic TMs with L1= L(M) Aton) L2=L(M2) and time complexities nki, nk Then we can test it wELI UL2 as follows: first test membership in Li and then test membership in L2. The time complexity in nohte, which is polynomial LIUL ₂ EP Notes: closed under union yes. concatenation. & yes Let L, L2 Ep and M, M2 be deterministic TMs with 41=L(Mi) - L =L(02). Suppose we are given as input we wilg... wn es langth a to check for membership in Li22. For each i-o.... test it wiwra t h AND with ..- wn Elz (Wort). 4 so accept, else refeet. It time time complexities too 4, L2 and nki, nke, then the overcell cost is. +) Cnk+h), which is polynomical time. Thug Life

closur properties for NP: Tage Union - identical argument concate nation. Similar argument. Here we can save some time by guessing nondeterministacally the splikt. So the overall cost is : xki take star: - similar argument again there is some saving in time complexity from the previous remark Complementation. we do not have NP complementation. closer for unt Intersaction - No

poge Star:-) yes Let the input be w of length n. It can beat most in th. not more. So we can check membersphop! for L, L' ,... Lie in UL. We know and that L2= LL is in P. So repeate the argrument to get that (3= LL... ch are en P. Then use the property that p is closed worto unions.ft follow that we can check membership as w in mial time. complementation: yes Given a polynomial time deterministic TM M for L we can check membership in Le by using the TM M' for which m' accept input wilt rol does not accept input w. Then sun time is the same (the machines are deterministic closed under Intersuction No.