1
$\begingroup$

I've recently started to deal with complexity theory and I'm trying to wrap my head around all the definitions and why they make sense.

One thing I don't quite understand is the importance/necessity of co-NP as its own set/class of problems. Couldn't for example TAUT be classified as a NP-complete problem just like SAT or is there some specific motivation to not put complements of a problem in the same set as the problem itself?

I'm sorry if this has been asked before or if my question is silly and doesn't make sense at all (In this case I'd like to know why if possible), I've really tried to look for it beforehand on the internet.

Kind regards,

$\endgroup$
2
$\begingroup$

Note that we don't know if $\text{NP=coNP}$. In fact, it is believed that they are not equal. Also note that the $\text{NP-complete}$ class requires its languages to be both $\text{NP-Hard}$ and in $\text{NP}$, so we can't say (unless proven $\text{NP=coNP}$) that $\text{TAUT}\in\text{NP}$.

The difference from $\text{P}$ is that to get the complement language, one can not just swap the $yes$ and $no$ instances of the Non-Deterministic Turing Machine, since its definition of accepting requires that there exists a computational path for which it accepts the input, and for rejecting it requires that all paths must not end in an accepting state.

One thing that is interesting about $\text{coNP}$ is that it describes the set of problems for which there is an easy way to verify that there is a $no$ instance for (i.e, verify a counter-example to the problem).

$\endgroup$
  • $\begingroup$ Hello, I really appreciate this answer. I do have another question now tho just to see if I understood this correctly; While in NP there is an easy way to verify that there is a yes instance in co-NP there is an easy way to verify a no instance? In the specific case of TAUT the "verification" would be to show a specific instance of a formula which will result in false, while in SAT we would be showing a specific instance of a formula which will result in true. $\endgroup$ – genericCSstudent May 26 '18 at 8:24
  • $\begingroup$ @genericCSstudent in $\text{SAT}$ we only need to show an example for an assignment that satisfies the formula. So in order to prove that something exists it is enough to show one instance of it. In $TAUT$ however, you want to show that something is a tautology, so you want to prove that any assignment results in a truth statement. This is where $\text{NP}$ and $\text{coNP}$ differ, so for $\text{TAUT}$, you only need one assignment that does not satisfy the formula to prove that the formula is not a tautology (i.e - easy to verify $no$ instance). $\endgroup$ – Mickey May 26 '18 at 8:43
  • $\begingroup$ Thanks so much! Think I get the idea now. And I'm really sorry for wasting your time with such a trivial question. $\endgroup$ – genericCSstudent May 26 '18 at 11:02
2
$\begingroup$

We don't define problems to be NP-complete. We define classes of problems, define the concept of completeness for those classes, and then prove that problems are complete, because they have the properties that define completeness.

Analogously, we don't define 13 to be prime; rather, we define the property of being prime and then prove that 13 has that property.

$\endgroup$

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.