Very few problems are in NP intersect coNP but not known to be in P. What to make of that?

Someone once told me:

 I was not surprised when Linear Programming was in P since it was already in \(  NP \cap  coNP  \), and problems in that intersection tend to be in P.

The same thing happened for PRIMALITY.

However FACTORING, viewed as the set 

\( \{ (n,m) \colon \hbox{there is a factor of n that is } \le m \} \),

is in \(  {\rm NP} \cap {\rm coNP} \).  Is that indicative that FACTORING is in P? I do not think so, though that's backwards-since I already don't think FACTORING is in P, I don't think being in the intersection is indicative of being in P.

Same for DISCRETE LOG, viewed as the set

\( \{ (g,b,y,p) : \hbox{p  prime, g is a gen mod p and } (\exists x\le y)[ g^x\equiv b \pmod p] \} \) 

which is in \( {\rm NP} \cap {\rm coNP} \).

1) Sets in  \({\rm NP} \cap {\rm coNP}  \) but not known to be in P:

FACTORING- thought to not be in P, though number theory can surprise you.  

DISCRETE LOG-thought to not be in P, but again number theory...

PARITY GAMES-thought to not be in P. (See Lance's post on the theorem that PARITY GAMES are in Quasi-poly time see here.) 

Darn, only three that I know of. If  you know others, then let me know.

2) Candidates for sets in \( {\rm  NP} \cap {\rm coNP} \) but not known to be in P:

Graph Isomorphism. Its in NP and its in co-AM. Under the standard derandomization assumptions GI is in AM=NP so then GI would be in \( {\rm NP} \cap {\rm coNP} \). Not known to be in P. Is it in P? I do not think there is a consensus on this. 

Darn, only one that I know of. If you know of others, then let me know, but make sure they are not in the third category below. 

3) Problems with an \( {\rm NP} \cap  {\rm coNP} \) feel to them but not known to be in P.

A binary relation B(x,y) is in TFNP if,  B(x,y)\in P and, for all x there is a y such that

|y| is bounded by a poly in |x|

B(x,y) holds.

So these problems don't really fit into the set-framework of P and NP.

TFNP has the feel of \( {\rm NP} \cap  {\rm coNP} \).

Nash Eq is in TFNP and is not known to be in P, and indeed thought to not be in P. There are other problems in here as well, and some complexity classes, and some completeness results. But these problems are not sets so not in the intersection. (I will prob have a future post on those other classes.)

--------------------------

So what to make of this? Why are so few problems in the intersection? Does the intersection = P (I do not think so)?

---------------------------

I close with another quote: 

as a former recursion theorist I hope that  \(NP \cap coNP\)=P, but as someone whose credit card numbers are on the web, I hope not.