Cheap and Secure Web Hosting Provider : See Now

# [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}$?

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