## Return to Answer

3 added 343 characters in body; added 4 characters in body

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.

2 added 149 characters in body; added 110 characters in body

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.

1

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.