This article is about a complexity class called coNP, which is related to the complexity class called NP. If you don't know what NP is, then read this article first.
A famous example of an NP problem is the decision travelling salesperson problem (DTSP). Given a list of cities and distances between them, and a distance budget d, the problem asks whether there's a route which visits every city exactly once, ends where it started, and has length at most d. Nobody knows whether there's an efficient (i.e. polynomial time) algorithm that solves all instances of this problem. However, if you're given a potential solution for an instance of the problem (i.e. a route which fits the bill for a given list of cities and distance d), you can check if it's correct in polynomial time.
Note that, like all NP problems, DTSP has a "yes/no" answer. While there's a polynomial time algorithm to check a potential "yes" answer, nobody knows of a polynomial time algorithm to solve the entire problem.
The co-NP version of DTSP asks the negation of DTSP: whether every valid route through the cities is longer than d. A "yes" answer for the co-NP version corresponds to a "no" answer to the original version and vice versa. So for the co-NP version there's a polynomial time algorithm to check a "no" answer, but no known polynomial time algorithm for solving the problem exists.
This illustrates the general definition of the class of co-NP problems: they are decision problems for which a "no" answer can be checked in polynomial time.
Could NP=coNP?
Could it be that the NP and coNP classes are actually the same?
Let's look at DTSP again. Since it's in NP we can check a "yes" answer, so that's a route that potentially fits the bill, in polynomial time. If it were also in coNP, then this would mean that we can check a "no" answer in polynomial time. A "no" answer says that there isn't such a route and it would have to come with a proof of this fact. One way of proving there isn't a valid route would be to list every possible route and rule it out — but this would give a proof that's far too long to check in polynomial time. It may be that a cleverer proof which does work in polynomial time exists, but most mathematicians don't think it likely.
This example illustrates the general intuition. While nobody has as yet been able to prove it, the consensus is that that NP probably isn't equal to coNP
How does this relate to P versus NP?
The question of whether P=NP is one of the biggest open problems in maths (find out more here). How does coNP fit into all this?
If it turns out that P=NP, then we immediately know that NP=coNP. That's because P=NP implies that every problem in the NP class can be solved in polynomial time. An answer to the NP version of the problem (such as "yes, a valid route through the cities exists" or "no, it doesn't exist") also gives you an answer to the coNP version. Therefore the coNP version would also be in the P class, giving P=NP=CoNP.
Conversely, if it turns out that NP ≠ coNP then we immediately know that P ≠ NP.
Could it be that P ≠ NP, but NP=coNP? This would mean that there's a problem that can't be solved in polynomial time, but for which we know for sure that both "yes" and "no" answers can be checked in polynomial time. It's a mathematical possibility, but it seems rather odd. So while nobody has been able to prove it, the general consensus is that both P ≠ NP and NP ≠ coNP.
This content forms part of our collaboration with the Isaac Newton Institute for Mathematical Sciences (INI) – you can find all the content from the collaboration here.
The INI is an international research centre and our neighbour here on the University of Cambridge's maths campus. It attracts leading mathematical scientists from all over the world, and is open to all. Visit www.newton.ac.uk to find out more.
