How do classes P, CoNP and NP relate? The answer depends not only one the conjecture that P ≠ NP but also on another conjecture.
Conjecture. NP ≠ CoNP
That conjecture is motivated by the observation that providing evidence that a puzzle has a solution appears to be quite different from providing evidence that it does not have a solution.
How would you provide evidence that a given clausal formula φ is unsatisfiable? Remember that the evidence would need to be short and easy to check. Showing that each assignment of values to the variables fails to satisfy φ will not work; the evidence is not of polynomial size in the length of the formula.
It does not appear that the unsatisfiability problem is in NP. But it is in CoNP; showing that a formula is not unsatisfiable is the same as showing that it is satisfiable, and we know that the satisfiability problem is in NP.
Theorem. If CoNP ≠ NP then P ≠ NP.
We prove the contrapositive, P = NP ⇒ CoNP = NP. So assume that P = NP.
P is closed under complementation. That is, if S ∈ P then S ∈ P.
Since P = NP, NP is also closed under complementation. So for every S, if S is in NP, then S is in NP.
But remember that CoNP consists of the complements of all problems in NP. So NP = CoNP.
It is easy to establish the following.
Theorem. P ⊆ CoNP.
Proof. We already know that P ⊆ NP. We also know that, if S ∈ P then S ∈ P: If you have an algorithm that solves S in polynomial time, then just switching the yes and no output gives an algorithm that solves S in polynomial time.
| S ∈ P | ⇒ | S ∈ P | |
| ⇒ | S ∈ NP | (since P ⊆ NP) | |
| ⇒ | S ∈ CoNP | (by the defn. of CoNP) |
The facts listed above imply that P ⊆ (NP ∩ CoNP). An obvious question is whether P = (NP ∩ CoNP). That appears to be false.
Conjecture. P ≠ (NP ∩ CoNP).
There are problems that are conjectured to be in NP ∩ CoNP but not in P. One is the problem of factoring an integer.
The factoring problem is a functional problem: given a positive integer x, output a nontrivial factor of x, or say that x is prime. (Equivalently, output the entire prime factorization of x.)
But P, NP and CoNP are classes of decision problems. For the factoring problem to be in (NP ∩ CoNP) − P, it must be converted into a decision problem.
Here is a decision problem that is roughly equivalent, in terms of time to solve, to factoring.
We can number the bits of a binary number from low order (bit 0) to high order.
Input. Positive integer x and nonnegative integer i.
Question. Is the i-th bit of the smallest prime factor of x a 1?
If you can solve the factoring functional problem in polynomial time, then you can certainly solve the factoring decision problem in polynomial time.
And if you can solve the factoring decision problem in polynomial time, then you can find the prime factors in polynomial time:
Get the smallest prime factor p of x one bit at a time.
If p = x, you are done; x is prime.
If p ≠ x, divide x by p and continue factoring what is left.
The conjecture that factoring is in (NP ∩ CoNP) − P is critical to public-key cryptography. It can be shown that public-key cryptograpy depends on a function that is in (NP ∩ CoNP) − P. Often, that problem is factoring.