# How to show that the complement of a language in $\mathsf P$ is also in $\mathsf P$? [duplicate]

If $L$ is a binary language (that is, $L \subseteq \Sigma = \{0,1\}^∗$) and $\overline{L}$ is the complement of $L$:

How can I show that if $L \in \mathsf P$, then $\overline{L} \in \mathsf P$ as well?

## marked as duplicate by Ran G., Hendrik Jan, sdcvvc, vonbrand, Yuval FilmusMar 4 '13 at 19:39

• Hint: if $L \in \mathsf P$, can you determine whether $x \notin L$ in polynomial time, for some input string $x$? – Niel de Beaudrap Mar 4 '13 at 13:32
Suppose you have an algorithm that decides membership in $L$ in polynomial time (by assumption since it's in $P$). You can easily write an algorithm that uses the previous one for deciding membership in $\bar L$ and prove that it takes polynomial time.