# Polynomial-time Verification

1 min read

Figure 34.3: Four possibilities for relationships among complexity classes. In each diagram, one region enclosing another indicates a proper-subset relation.

*(a)*P = NP = co-NP. Most researchers regard this possibility as the most unlikely.*(b)*If NP is closed under complement, then NP = co-NP, but it need not be the case that P = NP.*(c)*P = NP ∪ co-NP, but NP is not closed under complement.*(d)*NP ≠ co-NP and P ≠ NP ∪ co-NP. Most researchers regard this possibility as the most likely.Thus, our understanding of the precise relationship between P and NP is woefully incomplete. Nevertheless, by exploring the theory of NP-completeness, we shall find that our disadvantage in proving problems to be intractable is, from a practical point of view, not nearly so great as we might suppose.