In this problem, we fix some alphabet Σ and assume all languages called L or L i are subsets of Σ ∗ . Prove that the complexity class P is closed under complement. (That is, show that if L ∈ P then L c...

In this problem, we fix some alphabet Σ and assume all languages calledLorL_i
are subsets of Σ
^∗
.

1. Prove that the complexity class P is closed under complement. (That is, show that ifL
   ∈
   P thenL^c
   
   ∈
   P, whereL^c
   = Σ
   ^∗
   
   
   
   
   \ L.)


2. Prove that P is closed under union; i.e., ifL
   ₁
   , L
   ₂
   ∈
   P thenL
   ₁
   ∪
    L
   ₂
   ∈
   P.