One such problem I know is integer factorization.
What are other interesting cases?
[Math] Problems known to be in both NP and coNP, but not known to be in P
big-listcomputational complexitycomputer science
Related Solutions
I don't think there is any compelling evidence that integer factorization can be done in polynomial time. It's true that polynomial factoring can be, but lots of things are much easier for polynomials than for integers, and I see no reason to believe these rings must always have the same computational complexity. (Strangely, if you do believe that, it means the shortest lattice vector problem should also be efficiently solvable, but it doesn't seem to tell you anything about discrete logarithms. This puzzles me, since the parallels between factoring and discrete logs are also strong.) It's also true that primality testing can be done in polynomial time, but that is a fundamentally different problem: when a modulus is prime, it has enormous consequences for modular arithmetic, and it is not difficult to test for primality by looking for those consequences, but the actual methods shed no light on factoring.
On the other hand, there is also no compelling evidence that factoring can't be done in polynomial time (see http://research.microsoft.com/~cohn/Thoughts/factoring.html for a little more detail about this).
At our current level of knowledge, I view the complexity of factoring as a matter of opinion, speculation, and wishful thinking, not principled arguments. By contrast, there are exceedingly good reasons why the Riemann hypothesis should be true, and good reasons why P shouldn't equal NP. I'm certainly open to arguments that fall far short of rigorous proof; I've just never heard a convincing one about the complexity of factoring.
My interpretation of Sarnak's belief isn't that he sees some good reasons other people don't appreciate. Rather, it just feels plausible to him, and he's perhaps a little annoyed that lots of people firmly believe the opposite for no good reason, so he makes a point of stating a strong opinion.
Yes, the class NP $\cap$ coNP is closed under symmetric difference. To see this, suppose that $A$ and $B$ are both in NP $\cap$ coNP. This means that the truth of $a\in A$ can be verified in polynomial time with a suitable witness, and also $a\notin A$ can be verified in polynomial time with a suitable witness, and the same for $B$. Let $A\triangle B=(A-B)\cup (B-A)$ be the symmetric difference (the same as what you call $A\oplus B$), and argue as follows:
$A\mathrel{\triangle} B$ is in NP. This is because we can verify whether $a\in A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\notin B$ or that $a\notin A$ and $a\in B$. That is, the objects $a$ in the symmetric difference $A\mathrel{\triangle} B$ are verified by a pair of witnesses, which either verify membership in $A$ and not in $B$ or in $B$ but not in $A$.
$A\mathrel{\triangle} B$ is in coNP. This is because we can verfiy whether $a\notin A\mathrel{\triangle} B$ by verifying either that $a\in A$ and $a\in B$ or that $a\notin A$ and $a\notin B$.
So the symmetric difference is in NP $\cap$ coNP, as desired.
(Meanwhile, your proposed algorithm, if interpreted as a nondeterminisitic algorithm, is not correct, since failure to verify membership nondeterministically is not the same thing as a verfication of non-membership. In short, your algorithm can be fooled in the following way: suppose $x$ is in both languages, but in step 2 of your algorithm, $M_1$ happens to choose a branch of computation that doesn't verify membership---an inadequate witness, so it doesn't accept on that branch---but then $M_2$ does accept $x$ in step 4. In this case, you will accept $x$ when you shouldn't.)
Best Answer
One of my favorite problems in NP $\cap$ co-NP is deciding who wins a simple stochastic game. The game is played on a directed graph by two players, call them A and B. This graph contains several types of nodes. There is a source node and two sink nodes, one for each of the players. There are also random nodes (which include the source), "A" nodes, and "B" nodes. At the start of the game, for each "A" or "B" node, the corresponding player chooses one of the edges leading away from it, without seeing the other player's choices.
A token is then placed on the start node. The token undergoes a random walk. When it hits a random node, it chooses randomly among the edges directed away from this node. When it hits an "A" or "B" node, the token takes the chosen edge.
Each player's goal is to maximize the probability that the token lands on their sink node. The question in NP $\cap$ co-NP is: does player A have a winning strategy that ensures the token lands on his sink node with probability at least $\frac{1}{2}$?