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
