1

I need to prove if the P complexity class is closed under union and intersection. The problem is that I don't know how to start; What should I use to solve it? Do I need to use Functions in order to demonstrate it?, maybe problems?. And what do exactly "closed under P class" means?

Thanks for your time.

Alvarillo Fernandez
  • 11
  • 1
    If you understand the terms in the question, you should be able to just follow your nose. What needs to be true of a language for it to be in $\mathsf{P}$? If $L_1$ and $L_2$ are languages, what strings are in $L_1 \cup L_2$ and $L_1 \cap L_2$? Assuming $L_1,L_2 \in \mathsf{P}$, what can you infer about $L_1\cup L_2$ and $L_1 \cap L_2$? – mjqxxxx Apr 23 '18 at 16:21

1 Answers1

1

Showing that $\mathcal{P}$ is closed under intersection is straight-forward. Let $L_{1}, L_{2} \in \mathcal{P}$, and let $M_{1}, M_{2}$ be the deterministic Turing Machines. For $\omega \in \Sigma^{*}$, we run $M_{1}(\omega), M_{2}(\omega)$. Now $\omega \in L_{1} \cap L_{2}$ iff $M_{1}, M_{2}$ both accept $\omega$. As $M_{1}, M_{2}$ are polynomial time and deterministic, so is the procedure I described (which can be formalized as a product Turing Machine, in a similar manner as with finite state automata). So $\mathcal{P}$ is closed under intersection.

The proof for closure under union is analogous. The only difference is that at least one of $M_{1}, M_{2}$ must accept $\omega$, rather than both $M_{1}, M_{2}$ accepting $\omega$.

ml0105
  • 14,674