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

$\endgroup$
  • $\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 Aug 19 '10 at 20:22
  • 2
    $\begingroup$ Please could you define UP, or give a link. $\endgroup$ – Emil Aug 29 '10 at 17:35
15
$\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.

$\endgroup$
  • $\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 Aug 26 '10 at 17:21
13
$\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$.)

$\endgroup$
  • 3
    $\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 Aug 20 '10 at 1:24
  • 1
    $\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 Aug 20 '10 at 3:43
7
$\begingroup$

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

$\endgroup$
  • 3
    $\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 Dec 14 '11 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 Jan 17 '12 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 Dec 2 '13 at 20:27
  • $\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 Dec 5 '13 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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