# Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?

Are there any natural problems in $NP \cap coNP$ that are not (known to be/thought to be) in $UP \cap coUP$?

Obviously the big one everyone knows about in $NP \cap coNP$ is the decision version of factoring (does n have a factor of size at most k), but that is in fact in $UP \cap coUP$.

• Although technically this should be a community wiki since I'm looking for a list, I don't know of ANY such problems, so I'm not expecting more than one answer (and when it comes, it deserves some credit). If it ends up that there's a litany of such problems then I'll change it to a community wiki. – Joshua Grochow Aug 19 '10 at 20:22
• Please could you define UP, or give a link. – Emil Aug 29 '10 at 17:35

While parity games are known to be in both, it's been claimed that stochastic parity games are not known to be in UP intersect coUP.

• I'm accepting this as "the" answer because it's the only one that didn't involve promise problems :). (Sorry Andy.) Also, although answerers had no way of knowing this, it's exactly what I was looking for since I was inspired to ask this question after reading this answer to a different question: cstheory.stackexchange.com/questions/79/… (which was about parity games). – Joshua Grochow Aug 26 '10 at 17:21

Lattice problems are a good source of candidates. Given a basis for a lattice $L$ in $R^n$, one can look for a nonzero lattice vector whose ($\ell_2$) norm is smallest possible; this is the 'Shortest Vector Problem' (SVP). Also, given a basis for $L$ and a point $t \in R^n$, one can ask for a lattice vector as close as possible to $t$; this is the 'Closest Vector Problem' (CVP).

Both problems are NP-hard to solve exactly. Aharonov and Regev showed that in (NP $\cap$ coNP), one can solve them to within an $O(\sqrt{n})$ factor:

http://portal.acm.org/citation.cfm?id=1089025

I've read the paper, and I don't think there's any hint from their work that one can do this in UP $\cup$ coUP, let alone UP $\cap$ coUP.

A technicality: as stated, these are search problems, so strictly speaking we have to be careful about what we mean when we say they're in a complexity class. Using a decisional variant of the approximation problem, the candidate decision problem we get is a promise problem: given a lattice $L$, distinguish between the following two cases:

Case I: $L$ has a nonzero vector of norm $\leq 1$;

Case II: $L$ has no nonzero vector of norm $\leq C\sqrt{n}$. (for some constant $C > 0$)

This problem is in Promise-NP $\cap$ Promise-coNP, and might not be in either Promise-UP or Promise-coUP. But assume for the moment that it's not in Promise-UP; this doesn't seem to yield an example of a problem in (NP $\cap$ coNP)$\setminus$UP. The difficulty stems from the fact that NP $\cap$ coNP is a semantic class. (By contrast, if we identified a problem in Promise-NP$\setminus$Promise-P, then we could conclude P$\neq$NP. This is because any NP machine solving a promise problem $\Pi$ also defines an NP language $L$ which is no easier than $\Pi$.)

• Very interesting! I think the "technicality" of promise classes is very relevant, though. For example, Valiant-Vazirani shows that PromiseUP is NP-hard under randomized reductions, yet I doubt any such thing is true for UP. (Indeed, if VV can be derandomized and this were true, then we would have NP=UP. Of course, there aren't many known bad consequences of NP=UP, but it seems quite unlikely.) – Joshua Grochow Aug 20 '10 at 1:24
• That's a good point, and I hadn't thought about VV in quite those terms before (as talking about Promise-UP). Here by a randomized reduction to promise problem $\Pi$ we mean randomized reductions which work w.h.p. given any solver for $\Pi$; we can't insist that the solver only be fed instances obeying the promise $\Pi$, since in VV we expect some instances with non-unique solutions. – Andy Drucker Aug 20 '10 at 3:43

Under standard derandomization assumptions, Graph Isomorphism is in NP $\cap$ co-NP.

• Lance: do you have a pointer for how to show GI is not in UP or not in co-UP? It is not obvious to me how to show that GI cannot be logspace reduced to GI restricted to rigid graphs (those with no nontrivial automorphisms); there is a simple Turing reduction. – András Salamon Dec 14 '11 at 13:12
• I don't know any interesting consequences of GI in UP or for that matter, GI in P. – Lance Fortnow Jan 17 '12 at 17:47
• @AndrásSalamon: I just noticed your comment (from a couple years ago). I think I'm being very slow today, but I don't see the "simple Turing reduction" from GI to GI on rigid graphs. Could you elaborate? – Joshua Grochow Dec 2 '13 at 20:27
• @JoshuaGrochow: I am not sure of the details now, but I think this was just a reference to one of the standard ways to rigidify graphs, for instance replacing each edge by an appropriate gadget. I don't think I meant to imply anything about this being efficient. – András Salamon Dec 5 '13 at 15:01