[Solved]: Show complement of language in same complexity class?

Problem Detail: 

If $L$ is a binary language ($\Sigma = (0, 1)^*$) and $\overline{L}$ is the complement of $L$, the set of binary strings not in $L$.

How can I show that, if $L$ is in the complexity class $P$, then so is $\overline{L}$?

Asked By : Calum Murray

Answered By : Ran G.

Deciding $L$ means you have a way to answer "YES" or "NO" on each input.

$\bar L$ is the complement language of $L$: if some input is in $L$, then it is not in $\bar L$ (and vice versa)..

Thus, deciding $L$ and deciding $\bar L$ are equivalent up to the final answer. If an algorithm to decide one of them takes $x$ time, the similar algorithm (up to the final state) for the other language will take... the same time.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents