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.
Asked By : Raphael
Answered By : Yuval Filmus
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]
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/38248
0 comments:
Post a Comment
Let us know your responses and feedback