2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 7
    $\begingroup$ Hint: if $L \in \mathsf P$, can you determine whether $x \notin L$ in polynomial time, for some input string $x$? $\endgroup$
    – Niel de Beaudrap
    Commented Mar 4, 2013 at 13:32
  • $\begingroup$ Could you turn this into a question about more closures of P (union, intersection etc.)? $\endgroup$
    – frafl
    Commented Mar 4, 2013 at 13:50

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

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