<p>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).</p>

<p>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:</p>

<p><a href="http://portal.acm.org/citation.cfm?id=1089025">http://portal.acm.org/citation.cfm?id=1089025</a></p>

<p>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.  </p>

<p>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 <em>promise problem</em>: given a lattice $L$, distinguish between the following two cases:</p>

<p>Case I: $L$ has a nonzero vector of norm $\leq 1$;</p>

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

<p>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$.)</p>

CC BY-SA 2.5
2010-08-20T01:24:57.597Z
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
CC BY-SA 2.5
2010-08-20T03:43:08.043Z
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
CC BY-SA 2.5
2010-08-19T21:17:39.210Z
2010-08-19T21:23:19.493Z
2010-08-19T21:23:19.493Z
Andy Drucker
<p>Under standard derandomization assumptions, Graph Isomorphism is in NP $\cap$ co-NP.</p>

CC BY-SA 3.0
2011-12-14T13:12:34.040Z
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
CC BY-SA 3.0
2012-01-17T17:47:35.453Z
I don't know any interesting consequences of GI in UP or for that matter, GI in P.
Lance Fortnow
CC BY-SA 3.0
2013-12-02T20:27:32.777Z
@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
CC BY-SA 3.0
2013-12-05T15:01:33.787Z
@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
CC BY-SA 4.0
2023-07-07T22:42:39.770Z
But there is an $RP$ reduction from $NP$ to $UP$, which under derandomization assumptions would imply $UP=NP$. I suppose the same is true for the complements and therefore the intersection?
rus9384
CC BY-SA 3.0
2011-12-12T14:28:15.887Z
2011-12-12T14:28:15.887Z
Lance Fortnow
<p>While <a href="http://en.wikipedia.org/wiki/Parity_game">parity games</a> are known to be in both, <a href="http://portal.acm.org/citation.cfm?id=1109631">it's been claimed</a> that stochastic parity games are not known to be in UP intersect coUP.</p>

CC BY-SA 2.5
2010-08-26T17:21:47.920Z
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: http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/137#137 (which was about parity games).
Joshua Grochow
CC BY-SA 2.5
2010-08-19T21:11:20.187Z
2010-08-19T21:11:20.187Z
Lev Reyzin
<p>Are there any natural problems in $NP \cap coNP$ that are not (known to be/thought to be) in $UP \cap coUP$?</p>

<p>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$.</p>

CC BY-SA 4.0
2020-12-13T01:15:25.380Z
@Emil I recommend the complexity zoo if you see unfamiliar classes here. Wiki works for many as well, but doesn't have some of the more obscure classes. You can find UP here: https://complexityzoo.net/Complexity_Zoo:U
Jesse Stern
CC BY-SA 2.5
2010-08-19T20:22:51.287Z
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
CC BY-SA 2.5
2010-08-29T17:35:28.450Z
Please could you define UP, or give a link.
Emil
<cc.complexity-theory><complexity-classes><np>
Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?
Joshua Grochow
# Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?

(Asked by: username_0 on 2010-08-19)

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$.

**Tags:** cc.complexity-theory, complexity-classes, np

> **Comments:**
> **username_0**: 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.  
> **username_2**: Please could you define UP, or give a link.  
> **username_1**: @username_2 I recommend the complexity zoo if you see unfamiliar classes here. Wiki works for many as well, but doesn't have some of the more obscure classes. You can find UP here: https://complexityzoo.net/Complexity_Zoo:U  

---

## 3 answers

### Answer by username_7 on 2010-08-19. Score: 16 | Accepted answer

While [parity games](http://en.wikipedia.org/wiki/Parity_game) are known to be in both, [it's been claimed](http://portal.acm.org/citation.cfm?id=1109631) that stochastic parity games are not known to be in UP intersect coUP.

> **Comments:**
> **username_0**: 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: http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/137#137 (which was about parity games).  

---

### Answer by username_3 on 2010-08-19. Score: 14

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$.)

> **Comments:**
> **username_0**: 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.)  
> **username_3**: 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.  

---

### Answer by username_4 on 2011-12-12. Score: 7

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

> **Comments:**
> **username_5**: 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.  
> **username_4**: I don't know any interesting consequences of GI in UP or for that matter, GI in P.  
> **username_0**: @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?  
> **username_5**: @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_.  
> **username_6**: But there is an $RP$ reduction from $NP$ to $UP$, which under derandomization assumptions would imply $UP=NP$. I suppose the same is true for the complements and therefore the intersection?  

---

