# Does a language have the same time complexity as its complement language?

If $$L ⊆ \{0, 1\}^*$$ is a language, then we denote by $$\overline{L}$$ the complement of $$L$$

For example, the definition of $$coNP$$ is $$coNP =\{L | \overline{L} \in NP\}$$

The complement of $$SAT$$ language is $$\overline{SAT} = \{\phi | \phi$$ is not satisfiable$$\}$$

Of course, there are other $$P$$ languages

What I want to ask is，Does a language have the same time complexity as its complement language?

• What is the "time complexity" of a language? Do you mean the complexity class? Nov 11, 2022 at 14:14

Yes. Consider decidable language $$L$$ and its complement $$\bar L$$. Note that the decidability of $$L$$ implies the decidability of $$\bar L$$. Thus, there exists a TM $$D$$ that can decide $$L$$ in $$\text{TIME}(f(n))$$. Similarly, there exists a TM $$D'$$ that can decide $$\bar L$$ in $$\text{TIME}(g(n))$$. We now consider three cases:

1. $$f(n) \text{ is } \Omega(g(n))$$

We then construct a more efficient TM $$D_L$$ such that

$$\forall x \in \{0, 1\}^*. D_L(x) = \overline {D'(x)}$$

That is, $$D_L$$ simulates $$D'$$ on input $$x$$ and flips the answer. Then $$D_L$$ decides $$L$$ in $$\text{TIME}(g(n))$$

1. $$g(n) \text{ is } \Omega(f(n))$$

We then construct a more efficient TM $$D_{\bar L}$$ such that

$$\forall x \in \{0, 1\}^*. D_{\bar L}(x) = \overline {D(x)}$$

That is, $$D_{\bar L}$$ simulates $$D$$ on input $$x$$ and flips the answer. Then $$D_{\bar L}$$ decides $$\bar L$$ in $$\text{TIME}(f(n))$$.

1. $$f(n) \text { is } \Theta(g(n))$$

$$D$$ and $$D'$$ decide $$L$$ and $$\bar L$$ respectively in the same time asymptotically (i.e. $$\text{TIME}(f(n)) = \text{TIME}(g(n))$$).

Thus, both $$L$$ and $$\bar L$$ can always be decided in the same time asymptotically.