28
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Commented Aug 19, 2010 at 20:22
  • 2
    $\begingroup$ Please could you define UP, or give a link. $\endgroup$
    – Emil
    Commented Aug 29, 2010 at 17:35
  • 1
    $\begingroup$ @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: complexityzoo.net/Complexity_Zoo:U $\endgroup$
    – Jesse Stern
    Commented Dec 13, 2020 at 1:15

3 Answers 3

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$
    – Joshua Grochow
    Commented Aug 26, 2010 at 17:21
14
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ 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.) $\endgroup$
    – Joshua Grochow
    Commented Aug 20, 2010 at 1:24
  • 2
    $\begingroup$ 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. $\endgroup$
    – Andy Drucker
    Commented Aug 20, 2010 at 3:43
7
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Dec 14, 2011 at 13:12
  • $\begingroup$ I don't know any interesting consequences of GI in UP or for that matter, GI in P. $\endgroup$
    – Lance Fortnow
    Commented Jan 17, 2012 at 17:47
  • $\begingroup$ @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? $\endgroup$
    – Joshua Grochow
    Commented Dec 2, 2013 at 20:27
  • 1
    $\begingroup$ @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. $\endgroup$
    – András Salamon
    Commented Dec 5, 2013 at 15:01
  • $\begingroup$ 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? $\endgroup$
    – rus9384
    Commented Jul 7, 2023 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.