Is P complexity class closed under union and intersection?

5k Views Asked by At

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.

1

There are 1 best solutions below

0
On

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$.