A language complete for NP intersection co-NP - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T14:14:13Z http://mathoverflow.net/feeds/question/34889 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34889/a-language-complete-for-np-intersection-co-np A language complete for NP intersection co-NP Sid 2010-08-08T04:51:30Z 2010-08-08T06:39:59Z <p>Hi,</p> <p>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$?</p> <p>Thanks</p> http://mathoverflow.net/questions/34889/a-language-complete-for-np-intersection-co-np/34892#34892 Answer by Marcos Villagra for A language complete for NP intersection co-NP Marcos Villagra 2010-08-08T05:48:12Z 2010-08-08T06:39:59Z <p>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.</p> <p><strong>Update:</strong> take a look at <a href="http://kintali.wordpress.com/2010/06/06/np-intersect-conp/" rel="nofollow">link</a> talking about this kind of problems. Also, the book by <a href="http://www.cs.princeton.edu/theory/complexity/" rel="nofollow">Arora and Barak</a> is a good reference.</p> <p><strong>Update:</strong> The claim above "unless the polynomial hierarchy collapses" is too strong. There is no evidence of such consequence.</p> <p>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.</p> http://mathoverflow.net/questions/34889/a-language-complete-for-np-intersection-co-np/34895#34895 Answer by Ryan Williams for A language complete for NP intersection co-NP Ryan Williams 2010-08-08T06:22:19Z 2010-08-08T06:31:14Z <p>$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:</p> <blockquote> <p>Michael Sipser: On Relativization and the Existence of Complete Sets. ICALP 1982: 523-531</p> </blockquote> <p>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:</p> <blockquote> <p>Juris Hartmanis, Neil Immerman: On Complete Problems for NP$\cap$CoNP. ICALP 1985: 250-259</p> </blockquote> <p>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$.</p> <p>But since then, there hasn't been much progress on the question, to my knowledge. I'd be very happy if I were corrected...</p>