8
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
13
$\begingroup$

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]

Improve this answer
$\endgroup$
3
  • $\begingroup$ ok just wondering for completeness, is there a result that (as diagram indicates & under the plausible assumptions) NPI ∩ co-NP is nonempty? $\endgroup$
    – vzn
    Commented Apr 27, 2015 at 18:09
  • $\begingroup$ Yuval, after rereading I agree with vzn (wonder of wonders): so far, your answer does not assume that (NP ∩ co-NP) - P is not empty. Several candidates for NPI-problems are known to be in NP ∩ co-NP while not known to be in P, so the diagram probably fits the current expectation in the field (assuming what you do assume in the answer). But is it strictly necessary? To our current knowledge, could it be the case, even under your assumptions, that NP ∩ co-NP = P? Did I miss something? $\endgroup$
    – Raphael
    Commented May 4, 2015 at 10:24
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented May 4, 2015 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.