Hi,
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$?
Thanks
1
-
$\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$– user5810Commented Aug 8, 2010 at 5:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
$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...
$\begingroup$
$\endgroup$
9
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.
-
-
$\begingroup$ Please tell me the page on which this is proved in Arora and Barak. $\endgroup$ Commented Aug 8, 2010 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$ Commented Aug 8, 2010 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$ Commented Aug 8, 2010 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$ Commented Aug 8, 2010 at 6:15