Is there any language $L$ know to be complete for $NP \cap co-NP$, i.e. any language $L^{\prime} \in NP\cap co-NP$ reduces in polynomial-time to $L$ and it is known that $L\in NP\cap co-NP$?


  • $\begingroup$ As far as I can find, there aren't any semantic classes that are known to have complete problems and are not known to be equal to a syntactic class. $\endgroup$ – user5810 Aug 8 '10 at 5:29

$NP \cap coNP$ is not known to have complete languages, but I don't know of any consequences as strong as what Marcos claims. Juris Hartmanis and his students worked extensively on this problem in the early 80's. Two references I know are:

Michael Sipser: On Relativization and the Existence of Complete Sets. ICALP 1982: 523-531

This paper shows that there is an oracle relative to which $NP \cap coNP$ does not have complete sets. So proving that it does have complete sets would at least require non-relativizing techniques. Also, as mentioned by Peter in Marcos' comment, there's also Hartmanis and Immerman's work:

Juris Hartmanis, Neil Immerman: On Complete Problems for NP$\cap$CoNP. ICALP 1985: 250-259

They give several interesting structural results about the problem. For one, they complement Sipser's result, giving an oracle relative to which $NP \cap coNP$ has complete languages yet $P \neq NP \cap coNP \neq NP$. They also show that $NP \cap coNP$ has complete languages under many-one reductions iff it has complete languages under Turing reductions. This paper also cites the following neat characterization by Kowalczyk (1985): $NP \cap coNP$ has a complete language iff there is a recursively enumerable list of pairs of $NP$ machines {$(N_{i,1}, N_{i,2})$} such that $\overline{L(N_{i,1})} = L(N_{i,2})$ and $\bigcup_i L(N_i) = NP \cap coNP$.

But since then, there hasn't been much progress on the question, to my knowledge. I'd be very happy if I were corrected...

| cite | improve this answer | |

There are no complete problems for $NP\cap coNP$, unless the polynomial hierarchy collapses. You'll find that phrase in several textbooks on complexity theory.

Update: take a look at link talking about this kind of problems. Also, the book by Arora and Barak is a good reference.

Update: The claim above "unless the polynomial hierarchy collapses" is too strong. There is no evidence of such consequence.

A better way to put it would be, there are no problems known to be complete for $NP\cap coNP$. It seems that non-relativizing techniques are required to proof the existence or non-existence of complete sets.

| cite | improve this answer | |
  • $\begingroup$ Got a reference?... $\endgroup$ – Ryan Williams Aug 8 '10 at 5:54
  • $\begingroup$ Please tell me the page on which this is proved in Arora and Barak. $\endgroup$ – Ryan Williams Aug 8 '10 at 6:01
  • $\begingroup$ in the draft version, chapter 5, the polynomial hierarchy and alternations, page 5.2(92), where it says "Note that $\sum_2^p contains both the classes NP and coNP". There is no proof, but this implies that a complete problem collapses the hierarchy to the second level. $\endgroup$ – Marcos Villagra Aug 8 '10 at 6:05
  • $\begingroup$ One would think that any such reference would have to cite Hartmanis and Immerman: springerlink.com/content/w115v82352n00474 but I can't find one that does. $\endgroup$ – Peter Shor Aug 8 '10 at 6:13
  • 1
    $\begingroup$ Marcos: Of course $Sigma_2 P$ contains $NP$ and $coNP$. That does not mean "$NP \cap coNP$ has a complete language implies the polynomial hierarchy collapses". $\endgroup$ – Ryan Williams Aug 8 '10 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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