What is the difference between NP and coNP? Is coNP a subset of NP ? or vice versa? What is the significance of NP $\cap$ coNP when it comes to mathematics?
[Math] the difference between NP and coNP
automatacomputational complexity
automatacomputational complexity
What is the difference between NP and coNP? Is coNP a subset of NP ? or vice versa? What is the significance of NP $\cap$ coNP when it comes to mathematics?
Best Answer
NP is the class of decision problems for which there is a polynomial time algorithm that can verify "yes" instances given the appropriate certificate.
CoNP is the class of decision problems for which there is a polynomial time algorithm that can verify "no" instances given the appropriate certificate.
We don’t know whether coNP is different from NP.
There is a problem in NP for every problem in coNP, and vice versa. For example, the SAT problem asks "does there exist a boolean assignment which makes this formula evaluate to True?". The complement problem, which is in coNP, asks, "do all boolean assignments make this formula evaluate to False?"