Hi,
Is there any language $L$ know to be complete for $NP \cap coNP$, i.e. any language $L^{\prime} \in NP\cap coNP$ reduces in polynomialtime to $L$ and it is known that $L\in NP\cap coNP$?
Thanks
Hi, Is there any language $L$ know to be complete for $NP \cap coNP$, i.e. any language $L^{\prime} \in NP\cap coNP$ reduces in polynomialtime to $L$ and it is known that $L\in NP\cap coNP$? Thanks 


$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:
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 nonrelativizing techniques. Also, as mentioned by Peter in Marcos' comment, there's also Hartmanis and Immerman's work:
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 manyone 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... 


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 nonrelativizing techniques are required to proof the existence or nonexistence of complete sets. 

