0
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ What is the "time complexity" of a language? Do you mean the complexity class? $\endgroup$
    – Nathaniel
    Nov 11, 2022 at 14:14

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.