# What do we know about NP ∩ co-NP and its relation to NPI?

A TA dropped by today to inquire some things about NP and co-NP. We arrived at a point where I was stumped, too: what does a Venn diagram of P, NPI, NP, and co-NP look like assuming P ≠ NP (the other case is boring)?

There seem to be four basic options.

1. NP ∩ co-NP = P

In particular, co-NPI ∩ NPI = ∅

2. NP ∩ co-NP = P ∪ NPI

In particular, co-NPI = NPI?

3. NP ∩ co-NP ⊃ P ∪ NPI ∪ co-NPI

A follow-up question in this case is how NPC and co-NPC are related; is there an overlap?

4. Something else, that is in particular some problems from NPI are in co-NP and others are not.

Do we know which is right, or at least which can not be true?

The complexity zoo entries for NPI and NP ∩ co-NP do not inspire much hope that anything is known, but I'm not really fluent enough in complexity theory to comprehend all the other classes (and their impact on this question) floating around there.

• This paper shows among else that in some relativized world, P$\neq$NP$\cap$coNP$\neq$NP: link.springer.com/chapter/10.1007%2FBFb0015750. I don't know whether there is a relativized world such that NP$\neq$coNP but P=NP$\cap$coNP. – Yuval Filmus May 4 '15 at 13:14