0
$\begingroup$

I have recently read the definition of $coNP := \{L \ \mid \ \overline{L} \in P\}$, where $L$ denotes a language. However, I am wondering what the difference between $P$ and $coNP$ is, since an elementary result of the theory of Turing Machines is that if $L \in P$, then $\overline{L} \in P$.

So is $P = coNP$ or is there something that I am missing here?

$\endgroup$
3
$\begingroup$

$P=coNP$ is an open question, equivalent to the famous: "is $P=NP$ true?" question.

The definition of $coNP$ you have is incorrect. The correct definition is the following:

$$coNP:=\{L\mid \overline{L}\in NP\}$$ As you can see, it reads $NP$ and not $P$. It was probably a typo wherever you saw that definition.

$\endgroup$
1
  • $\begingroup$ Oh, thanks a lot. I was using the online (draft) version of Arora and Barak from theory.cs.princeton.edu/complexity The error there is on page 218. That clears it up, thanks for your help. $\endgroup$
    – 3nondatur
    Oct 18 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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