$\begingroup$

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.

$\endgroup$ 1

1 Answer

$\begingroup$

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

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy