HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
knowwhatitsnpiaboutandrelation

Problem

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.

-
NP ∩ co-NP = P

In particular, co-NPI ∩ NPI = ∅

-
NP ∩ co-NP = P ∪ NPI

In particular, co-NPI = NPI?

-
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?

-
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.

Solution

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:

[source]

Context

StackExchange Computer Science Q#38248, answer score: 13

Revisions (0)

No revisions yet.