patternModerate
What do we know about NP ∩ co-NP and its relation to NPI?
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.
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]
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.