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

Problem Detail: 

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?

Asked By : Calum Murray

Answered By : saadtaame

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10257