Skip to main content
4 of 4
fixes a small bug; adds a Venn diagram
Raphael
  • 72.9k
  • 30
  • 181
  • 393

The fact that P ≠ NP does not preclude the possibility that NP = co-NP, in which case NP ∩ co-NP = NP. So to further the discussion, let us assume that NP ≠ co-NP. In that case, Corollary 9 in Schöning's A uniform approach to obtain diagonal sets in complexity classes shows that there exists some language in NP – co-NP which is NP-intermediate. So NPI strictly contains (NP ∩ co-NP) - P (note that every language in NP ∩ co-NP is in P ∪ NPI). This is your option (4).

In summary, assuming P ≠ NP and NP ≠ co-NP, we get this:

enter image description here
[source]

Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512