2
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Ran G., Hendrik Jan, sdcvvc, vonbrand, Yuval Filmus Mar 4 '13 at 19:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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 Mar 4 '13 at 13:32
  • $\begingroup$ Could you turn this into a question about more closures of P (union, intersection etc.)? $\endgroup$ – frafl Mar 4 '13 at 13:50
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.

$\endgroup$

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